Pagini recente » Cod sursa (job #1743023) | Cod sursa (job #116109) | Cod sursa (job #450213) | Cod sursa (job #458699) | Cod sursa (job #1741201)
#include<stdio.h>
using namespace std;
FILE *f1=fopen("bfs.in","r");
FILE *f2=fopen("bfs.out","w");
int n,m,s,i,j,v[100001],coada[100001],nrc;
struct nod{
int inf;
nod *urm;
}*L[100001];
void adaugsf(int val,nod *&vf){
nod *q;
q=new nod;
q->inf=val;
q->urm=vf;
vf=q;
}
void cit(){
int i,a,b;
fscanf(f1,"%d%d%d",&n,&m,&s);
for (i=1;i<=n;i++)
L[i]=0;
for (i=1;i<=m;i++){
fscanf(f1,"%d%d",&a,&b);
adaugsf(b,L[a]);
}
fclose(f1);
}
void bfs(){
int i,x,p,u;
nod *q;
v[s]=1;p=u=1;
coada[u]=s;
while(p<=u){
x=coada[p];
q=L[x];
while(q!=0){
if (v[q->inf]==0){
v[q->inf]=v[x]+1;
u++;
coada[u]=q->inf;
}
q=q->urm;
}
p++;
}
}
int main(){
cit();
bfs();
for (i=1;i<=n;i++)
if (i==s) fprintf(f2,"0 ");
else
if (v[i]==0) fprintf(f2,"-1 ");
else
fprintf(f2,"%d ",v[i]-1);
fclose(f2);
return 0;
}