Cod sursa(job #2671820)

Utilizator sorinturdaSorin Turda sorinturda Data 12 noiembrie 2020 18:35:55
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");
const int NN=99999;

int n,m,s,v[NN],p[NN],x,y;
queue <int>q;
vector <int>a[NN];


void bfs(int nod){
  q.push(nod);
  v[s]=0;
  while(!q.empty()){
    int vf=q.front();
    q.pop();
    for(int i=0;i<a[vf].size();i++){
      if(v[a[vf][i]]==-1)
        q.push(a[vf][i]),v[a[vf][i]]=v[vf]+1;
    }
  }
}

int main() {
  in>>n>>m>>s;
  while(m--){
    in>>x>>y;
    a[x].push_back(y);
  }
  x=0;
  for(int i=1;i<=NN;i++)
    v[i]=-1;
  bfs(s);
  for(int i=1;i<=n;i++){
    if(i==s)
      out<<0<<' ';
    else
      if(!v[i])
        out<<-1<<' ';
      else
        out<<v[i]<<' ';
  }
  return 0;
}