Pagini recente » Rating Petrescu Theodor (Theo0_0) | Cod sursa (job #1438589) | Istoria paginii runda/cnrv_1/clasament | Cod sursa (job #1252134) | Cod sursa (job #671509)
Cod sursa(job #671509)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
int n,m,S[100001],d[100001],start;
int c[100001],li=1,ls=0;
struct nod
{
int inf;
nod* next;
};
nod* LA[100001];
int coadavida()
{
return li>ls;
}
void pune(int x)
{
ls++;
c[ls]=x;
}
int extragere()
{
int x=c[li];
li++;
return x;
}
void BF(int start)
{
S[start]=1;
pune(start);
while(!coadavida())
{
int x=extragere();
nod* nc=LA[x];
while(nc)
{
int vecin=nc->inf;
if(!S[vecin])
{
S[vecin]=1;
d[vecin]=d[x]+1;
pune(vecin);
}
nc=nc->next;
}
}
}
void add(int x,int y)
{
nod* n=new nod;
n->inf=y;
n->next=LA[x];
LA[x]=n;
}
void citire()
{
in>>n>>m>>start;
for(int i=1;i<=m;i++)
{
int x,y;
in>>x>>y;
add(x,y);
}
}
int main()
{
citire();
BF(start);
for(int i=1;i<=n;i++)
if(d[i]==0 && i!=start)
d[i]=-1;
for(int i=1;i<=n;i++)
out<<d[i]<<" ";
return 0;
}