Cod sursa(job #498243)

Utilizator skullLepadat Mihai-Alexandru skull Data 4 noiembrie 2010 18:05:24
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
#define inf 2000000000
#define nmax 100005

int n, m, s;
int drum[nmax], viz[nmax];
vector<int> G[nmax];

void citire ()
{
	int i, x, y;
	freopen("bfs.in","r",stdin);
	scanf("%d%d%d", &n, &m, &s);
	for (i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
	}
}

void bfs ()
{
	int i, min , x;
	queue<int> Q;
	viz[s] = 1;
	Q.push(s);
	while (!Q.empty() )
	{
		min = Q.front (); Q.pop ();
		for (i = 0; i < G[min].size (); ++i)
		{
			x = G[min][i];
			if (!viz[x]) { viz[x] = 1; drum[x] = drum[min] + 1; Q.push(x); }
		}
	}
}

void afisare ()
{
	int i;
	freopen("bfs.out","w",stdout);
	for (i = 1; i <= n; ++i)
		if (viz[i] == 1) printf("%d ", drum[i]);
			else printf("-1 ");
}
	
int main ()
{
	citire ();
	bfs ();
	afisare ();
	return 0;
}