Cod sursa(job #1760251)

Utilizator irinapatularuPatularu Irina irinapatularu Data 20 septembrie 2016 16:37:57
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define NMAX 100001
using namespace std;
int n, m, s;

vector<int> adList[NMAX];
int distances[NMAX];
queue<int> Q;

void bfs(){
	Q.push(s);
	distances[s] = 0;

	while(!Q.empty()){
		int node = Q.front();
		Q.pop();

		vector<int> :: iterator it = adList[node].begin();

		while(it != adList[node].end()){
			if(distances[*it] == -1){
				Q.push(*it);
				distances[*it] = distances[node] + 1;
			}

			it++;
		}
	}

}
int main(){
	int x, y;

	ifstream f("bfs.in");
	ofstream g("bfs.out");

	f >> n >> m >> s;

	for(int i = 0; i < m; i++){
		f >> x >> y;
		adList[x].push_back(y);
	}
	f.close();

	for(int i = 1; i <= n; i++)
		distances[i] = -1;

	bfs();

	for(int i = 1; i <= n; i++)
		g << distances[i] <<" ";
	g.close();

	return 0;
}