Pagini recente » Borderou de evaluare (job #2498708) | Rating Nitu Theodor (TheoGT) | Diferente pentru problema/aprindere intre reviziile 21 si 20 | Cod sursa (job #1306352)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n, m, i, j, k, ok, minim, s;
int vizit[100100], cost[100100];
int coada[100100], x, y, p, u;
vector < int > v[100100];
void write(){
for(i = 1; i <= n; i ++)
fout << cost[i] << " ";
return;
}
void initialize(){
p = 1; u = 1; coada[1] = s;
for(i = 1; i <= n; i ++)
cost[i] = -1;
return;
}
void bfs(int val){
vizit[val] = 1;
for(int i = 0; i < v[val].size(); i ++){
if(vizit[v[val][i]] == 0){
cost[v[val][i]] = cost[val] + 1;
u ++; coada[u] = v[val][i];
}
}
if(++ p <= u)
bfs(coada[p]);
return;
}
void read(){
fin >> n >> m >> s;
initialize(); cost[s] = 0;
for(i = 1; i <= m; i ++){
fin >> x >> y;
v[x].push_back(y);
}
return;
}
int main(){
read();
bfs(s);
write();
return 0;
}