#19

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 

#include <bits/stdc++.h>

using namespace std;

ifstream fin("BFS.in");
ofstream fout("BFS.out");

int n,m,a[101][101],k,x[100],v[100];
int bfs(int start)
{
  int i,k,st,dr;
    st=dr=1;
  x[1]=start;
  v[start]=1;
  while(st<=dr)
  {
    k=x[st];
    for(i=1;i<=n;i++)
      if(v[i]==0 && a[k][i]==1)
      {
          fout<<i<<" ";
        v[i]=1;
        x[++dr]=i;
      }
    st++;
  }
}
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;
        }
        fout<<k<<" ";
        bfs(k);
        return 0;
}