Cod sursa(job #2434031)

Utilizator KataIsache Catalina Kata Data 30 iunie 2019 13:48:11
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector <int> edge[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;
       edge[x].push_back(y);
      }
  Q.push(S);
  us[S]=1;
  while(!Q.empty())
      {
       x=Q.front();
       Q.pop();
       for(i=0;i<edge[x].size();i++)
         if(!us[edge[x][i]])
           {
             dist[edge[x][i]]=dist[x]+1;
             us[edge[x][i]]=1;
             Q.push(edge[x][i]);
           }
      }
  for(i=1;i<=n;i++)
  {if(dist[i]==0 &&i!=S) dist[i]=-1;
    fout<<dist[i]<<" ";}
  return 0;
}