Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

Date de intrare

Fişierul de intrare lungimeminima.in conţine pe prima linie numerele n p L, cu semnificația precizată. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire lungimeminima.out va conţine pe prima linie numărul de vârfuri determinate. A doua linie va conține în ordine crescătoare vârfurile determinate, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta;
• pentru toate datele de test există cel puțin un vârf q cu proprietatea dorită;

Exemplu

lungimeminima.in

7 4 2
1 2
1 7
1 4
3 5
4 5
4 7
5 6
5 7

lungimeminima.out

3
2 3 6

#include <bits/stdc++.h>

using namespace std;

ifstream cin("lungimeminima.in");
ofstream cout("lungimeminima.out");

int n , m , x , y , a[101][101] , v[101] , d[101] , p , L , cnt;

void bfs(int x)
{
    v[x] = 1;
    d[x] = 1;
    queue <int> Q;
    Q.push(x);
    while(!Q.empty())
    {
        int aux = Q.front();
        Q.pop();
        for(int i = 1 ; i <= n ; i++)
            if(!v[i] && a[aux][i] == 1)
            {
                v[i] = 1;
                Q.push(i);
                d[i] = d[aux] + 1;
            }
    }

}

int main()
{
    cin >> n >> p >> L;

    while(cin >> x >> y)
    {
        a[x][y] = a[y][x] = 1;
    }

    bfs(p);

    for(int i = 1 ; i <= n ; i++)
        if(d[i] == L + 1) cnt++;

    cout << cnt << '\n';
    for(int i = 1 ; i <= n ; i++)
        if(d[i] == L + 1) cout << i << " ";
}