Cod sursa(job #854000)
| Utilizator | Data | 12 ianuarie 2013 17:19:27 | |
|---|---|---|---|
| Problema | BFS - Parcurgere in latime | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.63 kb |
#include <cstdio>
#include <cstdlib>
FILE*f=fopen("bfs.in","r");
FILE*g=fopen("bfs.out","w");
int a[3][100001];
int b[100001],i,m,n,s,ok;
int main()
{
fscanf(f,"%d%d%d",&n,&m,&s);
for (i=1;i<=m;i++)
fscanf(f,"%d%d",&a[1][i],&a[2][i]);
b[s]=1;
ok=1;
while (ok)
{
ok=0;
for (i=1;i<=m;i++)
if (b[a[1][i]]!=0 && (b[a[2][i]]==0 || b[a[2][i]]>b[a[1][i]]+1))
{
b[a[2][i]]=b[a[1][i]]+1;
ok=1;
}
}
for (i=1;i<=n;i++)
fprintf(g,"%d ",b[i]-1);
return 0;
}
