Pagini recente » Diferente pentru problema/talent intre reviziile 3 si 4 | Istoria paginii runda/oni_2005_1_10 | Cod sursa (job #625769) | Cod sursa (job #1811600)
#include <bits/stdc++.h>
#define nmax 100000
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
queue <int> q;
int n,m,s,v[nmax],cost[nmax];
vector <int> a[nmax];
void bfs(int x){
q.push(s);
v[s]=1;
memset(cost, -1, sizeof(cost));
cost[s]=0;
while(!q.empty()){
int top=q.front();
q.pop();
for (int j = 0; j < a[top].size(); j++)
if(cost[a[top][j]] == -1){
cost[a[top][j]]=cost[top]+1;
if(!v[a[top][j]]) {
q.push(a[top][j]);
v[a[top][j]]=1;
}
}
}
}
int main()
{
int x,y;
fin>>n>>m>>s;
for(int i=0;i<m;i++){
fin>>x>>y;
a[x].push_back(y);
}
bfs(s);
for(int i=1;i<=n;i++)
fout<<cost[i]<<' ';
fout.close();
fin.close();
return 0;
}