Cod sursa(job #333379)

Utilizator levap1506Gutu Pavel levap1506 Data 22 iulie 2009 15:18:06
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
int N,M,S,a,b, Nx[100010], Q[100010], Ql[100010],i;
vector<int> V[100010];
vector<int>::iterator it;
int main() {
  ifstream in;
  ofstream out;
  in.open("tests/grader_test3.in");
  out.open("bfs.out");
  in >> N >> M >> S;
  for (i=0; i<M; i++) {
      in >> a >> b;
      V[a].push_back(b);
  }

  Q[++Q[0]]=S;
  for (i=0;i<=N;i++)
   Nx[i]=-1;
  Nx[S]=0;
  Ql[S]=0;
  i=0;
  while (i<Q[0]) {
      i++;
      S=Q[i];
      for (it=V[S].begin(); it!=V[S].end(); it++) {
          if (Nx[*it]==-1) {
              Nx[*it]=Ql[i]+1;
              Q[++Q[0]]=*it;
              Ql[Q[0]]=Ql[i]+1;
          }
      }
  }
  for (i=1;i<=N;i++) {
      out << Nx[i] << " ";
  }
  out.close();
return 0;
}