Pagini recente » Lant2 | Calafat | Charlie | Becuri | Cod sursa (job #694822)
Cod sursa(job #694822)
#include <fstream>
#include <stdio.h>
using namespace std;
FILE * bfs;
ofstream g("bfs.out");
struct nod
{
long inf;
nod *urm;
};
nod *p[100003];
long cost[100003];
long i,m,n,s;
void citire()
{
nod *q;
nod *ultim[100003];
for (i=1;i<=m;i++)
{
p[i]=new nod;
p[i]->inf=0;
p[i]->urm=NULL;
ultim[i]=p[i];
}
long x,y;
for (i=1;i<=m;i++)
{
fscanf(bfs,"%ld %ld",&x,&y);
q=new nod;
q->inf=y;
q->urm=NULL;
ultim[x]->urm=q;
ultim[x]=q;
}
}
void sterg()
{
nod *q;
for (i=1;i<=m;i++)
{
q=p[i];
p[i]=p[i]->urm;
q->urm=NULL;
delete q;
}
}
void bf(long start)
{
long pr,u,c[100003],viz[100003],x;
nod *q;
c[1]=start;
viz[start]=1;
pr=1;
u=1;
cost[start]=0;
while (pr<=u)
{
x=c[pr];
q=p[x];
while (q)
{
if (!viz[q->inf])
{
u++;
c[u]=q->inf;
viz[q->inf]=1;
cost[q->inf]=cost[x]+1;
}
q=q->urm;
}
pr++;
}
}
int main()
{
bfs=fopen("bfs.in","r");
fscanf(bfs,"%ld %ld %ld",&n,&m,&s);
citire();
sterg();
bf(s);
for (i=1;i<=n;i++)
{
if (i!=s && !cost[i]) g<<"-1 ";
else g<<cost[i]<<' ';
}
g<<'\n';
g.close();
return 0;
}