Question

Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.
Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X.
Date de intrare

Fişierul de intrare BFS.in conţine pe prima linie trei numere naturale n m X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere x y cu semnificația că există muchie între x și y .
Date de ieşire

Fişierul de ieşire BFS.out va conţine pe prima linie vârfurile vizitate în urma parcurgerii în lățime a grafului, aceasta începând din vârful X.
Restricţii şi precizări

2 <= n <= 100
1 <= m <= n*(n-1)/2
Graful poate sa nu fie conex!!!
dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.


Exemplu

BFS.in

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

BFS.out

2 1 3 4 5

Answer 1

#include <fstream>using namespace std;ifstream fin("BFS.in");ofstream fout("BFS.out");int n,m,a[101][101],k;void bf(int x){    int c[101],viz[101]={0},p,u,z,i;    p=u=1;    c[p]=x;    viz[x]=1;    while(p<=u)    {        z=c[p];        for(i=1;i<=n;i++)            if(a[z][i]==1 && viz[i]==0)        {            u++;c[u]=i;viz[i]=1;        }        p++;    }    for(i=1;i<=u;i++)        fout<<c[i]<<' ';}int main(){    int i,x,y;    fin>>n>>m; fin>>k;    for(i=1;i<=m;i++)    {        fin>>x>>y;        a[x][y]=1;a[y][x]=1;    }
    bf(k);    return 0;}