Cod sursa(job #2458619)

Utilizator KataIsache Catalina Kata Data 21 septembrie 2019 10:53:36
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector <int> M[100002];
queue <int> Q;
bool us[100002];
int dist[100002];

int main()
{
  int n,i,m,x,y,S;
  fin>>n>>m>>S;
  for (i=1; i<=m; i++)
      {
       fin>>x>>y;
       M[x].push_back(y);
      }
  Q.push(S);
  us[S]=1;
  while(!Q.empty())
      {
       x=Q.front();
       Q.pop();
       for (i=0; i<M[x].size(); i++)
          if (!us[M[x][i]])
           {
             dist[M[x][i]]=dist[x]+1;
             us[M[x][i]]=1;
             Q.push(M[x][i]);
           }
      }
  for (i=1; i<=n; i++)
      {
        if (dist[i]==0 && i!=S)
            dist[i]=-1;
        fout<<dist[i]<<" ";
      }
  return 0;
}