Cerința

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați vârfurile din graf care se află la distanță k față de vârful 1. Distanța dintre două vârfuri x și y este egală cu lungimea celui mai scurt drum care are ca extremitate inițială pe x și ca extremitate finală pe y.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran în ordine crescătoare și separate prin câte un spațiu vârfurile din graf care se află la distanță k față de vârful 1. Dacă nu există nici un vârf care să îndeplinească condiția, atunci se va afișa Nu exista.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 100

Exemplu

Intrare

8 12 2
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
1 8

Ieșire

2 5 6

Explicație

Drumurile de lungime minimă care au lungimea egală cu 2 și o extremitate în vârful 1 sunt:
[1, 4, 2]
[1, 8, 2]
[1, 3, 5]
[1, 4, 6]
[5, 7, 1]

#include <bits/stdc++.h>


using namespace std;

vector <int> G[101];
vector <int> H[101];

int n , m , x , y , k , c , cnt , d[101] , v[101] , ok , d2[101] , v2[101];

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

void bfs2(int nod)
{
    d2[nod] = 0;
    v2[nod] = 1;
    queue <int> q;
    q.push(nod);
    while(!q.empty())
    {
        int x = q.front();
        for(auto i : H[x])
            if(!v2[i])
            {
                d2[i] = d2[x] + 1;
                v2[i] = 1;
                q.push(i);
            }
        q.pop();
    }
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        H[y].push_back(x);
    }

    bfs1(1);
    bfs2(1);
    for(int i = 1 ; i <= n ; i++)
    {
        if(d[1] != 0 && d2[i] != 0)
        {
            if(min(d[i] , d2[i]) == k) cout << i << " " , ok++;
            ok++;
        }
        else if(d[i] != 0 && d[i] == k) cout << i << " " , ok++;
        else if(d2[i] != 0 && d2[i] == k) cout << i << " " , ok++;
    }
    if(ok == 0) cout << "Nu exista";
}