Cod sursa(job #2021206)
| Utilizator | Data | 12 septembrie 2017 21:21:25 | |
|---|---|---|---|
| Problema | BFS - Parcurgere in latime | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.73 kb |
#include <fstream>
using namespace std;
ifstream in ("bfs.in");
ofstream out("bfs.out");
int a[10001][10001],c[10001],viz[10001],d[10001];
int main()
{
int n,m,p,u,x,e,b;
in>>n>>m>>x;
c[1]=x;
viz[x]=1;
p=u=1;
for (int i=1;i<=m;i++)
{
in>>e>>b;
a[e][b]=1;
}
while (p<=u)
{
x=c[p];
p++;
for (int i=1;i<=n;i++)
{
if (a[x][i]==1&&viz[i]==0)
{
u++;
c[u]=i;
viz[i]=1;
d[i]=d[x]+1;
}
}
}
for (int i=1;i<=n;i++)
if (viz[i]==0) d[i]=1;
for (int i=1;i<=n;i++)
out<<d[i]<<" ";
return 0;
}
