Cod sursa(job #1276484)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 26 noiembrie 2014 14:46:55
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>



using namespace std;
FILE *f=fopen("bfs.in","r");
FILE *g=fopen("bfs.out","w");

vector<int>a[100005];
vector<int>::iterator it;
int nr[100005],uz[100005],n,m,s,i,x,y;

void bf()
{
vector<int>::iterator it;
int p,u,c[100005];

p=1;
u=1;
c[p]=s;

while(p<=u)
{
for(it=a[c[p]].begin();it!=a[c[p]].end();++it)
if (uz[*it]==0)
{
 u++;
 c[u]=*it;
 uz[*it]=1;
 nr[*it]=nr[c[p]]+1;
}
p++;
}

}

int main()
{
fscanf(f,"%d%d%d",&n,&m,&s);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
}
uz[s]=1;
bf();

for(i=1;i<=n;i++)
{
if (i!=s && nr[i]==0)nr[i]=-1;
fprintf(g,"%d ",nr[i]);
}
fclose(g);
return 0;
}