Cerința

Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.

Date de intrare

Programul citește de la tastatură numărul n de noduri, nodul p și numărul m de arce, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc orientat de la nodul i la nodul j.

Date de ieșire

Programul va afișa pe ecran numărul C de noduri care respectă cerința, iar pe rândul următor cele C noduri, în ordine crescătoare, separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• prin drum minim se înțelege drum de cu lungimea minimă

Exemplu

Intrare

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

Ieșire

3
1 4 6

#include <bits/stdc++.h>


using namespace std;

vector <int> G[101];

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

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

int main()
{
    cin >> n >> p >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
    }
    bfs(p);
    for(int i = 1 ; i <= n ; i++)
        if((d[i] - 1) % 2 == 0 && i != p) cnt++ , rez[cnt] = i;

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