Mai intai trebuie sa te autentifici.
Cod sursa(job #1116661)
Utilizator | Data | 22 februarie 2014 18:52:27 | |
---|---|---|---|
Problema | BFS - Parcurgere in latime | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.83 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 100001
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
vector <int> vecin[nmax];
queue <int> q;
int n,m,s,a,b,i,nod[nmax];
void bfs(){
while (!q.empty()){
int cur=q.front();
q.pop();
for (i=0; i<vecin[cur].size(); i++)
if (nod[vecin[cur][i]]<0){
nod[vecin[cur][i]]=nod[cur]+1;
q.push(vecin[cur][i]);
}
}
}
int main(){
in >> n >> m >> s;
q.push(s);
for (i=1; i<=n; i++)
nod[i]=-1;
nod[s]=0;
for (i=1; i<=m; i++){
in >> a >> b;
vecin[a].push_back(b);
}
bfs();
for (i=1; i<=n; i++)
out << nod[i] << " ";
return 0;
}