Pagini recente » Cod sursa (job #1260256) | Cod sursa (job #2684957) | Istoria paginii runda/oji_andrei2 | Cod sursa (job #1483912) | Cod sursa (job #527938)
Cod sursa(job #527938)
#include<cstdio>
#include<vector>
using namespace std;
int n,m,S,c[100005],viz[100005],g[100005];
vector <int> A[100005];
void citire()
{
freopen("bfs.in" , "r" , stdin );
freopen("bfs.out" , "w" , stdout );
int i,x,y;
scanf("%d%d%d" , &n , &m , &S);
for( i = 1 ; i <= m ; i++ )
{
scanf("%d%d" , &x , &y);
A[x].push_back(y);
}
for( i = 1 ; i <= n ; i++ )
g[i] = A[i].size();
}
void BFS(int nod)
{
int i,p,u,x;
for( i = 1 ; i <= n ; i++ )
viz[i] = -1;
p = u = 1;
c[p] = nod;
viz[nod] = 0;
while( p <= u )
{
x = c[p];
for( i = 0 ; i < g[x] ; i++ )
if( viz[A[x][i]] == -1 )
{
c[++u] = A[x][i];
viz[A[x][i]] = viz[x]+1;
}
p++;
}
}
int main()
{
citire();
BFS(S);
int i;
for( i = 1 ; i <= n ; i++ )
printf("%d " , viz[i]);
printf("\n");
return 0;
}