Cod sursa(job #709442)

Utilizator fhandreiAndrei Hareza fhandrei Data 8 martie 2012 09:17:56
Problema BFS - Parcurgere in latime Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
//Include
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

//Constante
const int MAX_SIZE = 100000;

//Variabile
FILE *in, *out;

int nrNoduri, nrMuchii, nodInitial;
int nodCurent;
int dist[MAX_SIZE];

vector<int> graf[MAX_SIZE];
vector<int>::iterator it, end;

queue<int> q;

//Main
int main()
{
	in = fopen("bfs.in","rt");
	out = fopen("bfs.out","wt");
	fscanf(in, "%d%d%d", &nrNoduri, &nrMuchii, &nodInitial);
	
	int c_from, c_to;
	for(int i=1 ; i<=nrMuchii ; ++i)
	{
		fscanf(in, "%d%d", &c_from, &c_to);
		graf[c_from].push_back(c_to);
	}
	
	dist[nodInitial] = 1;
	q.push(nodInitial);
	while(!q.empty())
	{
		nodCurent = q.front();
		
		end = graf[nodCurent].end();
		for(it=graf[nodCurent].begin() ; it!=end ; ++it)
			if(!dist[*it])
			{
				dist[*it] = dist[nodCurent] + 1;
				q.push(*it);
			}
		q.pop();
	}
	
	for(int i=1 ; i <= nrNoduri ; ++i)
		fprintf(out, "%d ", dist[i] - 1);
	
	fclose(in);
	fclose(out);
	return 0;
}