Pagini recente » Concursuri Virtuale | Cod sursa (job #705891)
Cod sursa(job #705891)
#include<stdio.h>
#include <vector>
#include <queue>
using namespace std;
long i,n,m,x,y,s,pas,rez[100000];
vector<long> a[100000];
queue<long> q;
int main()
{
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
scanf("%ld %ld %ld",&n,&m,&s);
for(i=1;i<=n;i++) rez[i]=-1;
for(i=1;i<=m;i++)
{
scanf("%ld %ld",&y,&x);
a[y].push_back(x);
}
q.push(s);
pas=1; rez[s]=0;
while(!q.empty())
{
x=q.front();
while(!a[x].empty())
{
y=a[x].back();
if(rez[y]==-1)
{
rez[y]=pas;
q.push(y);
}
a[x].pop_back();
}
pas++;
q.pop();
}
for(i=1;i<=n;i++) printf("%ld ",rez[i]);
printf("\n");
return 0;
}