Cod sursa(job #694898)

Utilizator DevilShadowJunc Raul Cosmin DevilShadow Data 28 februarie 2012 08:52:01
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#define nm 100005

using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");

vector <int> v[nm];
int n, m, s, viz[nm];

void bfs(int s)
{
	int nod, c[nm], p, u;
	c[0] = s;
	viz[s] = 0;
	p = 0;
	u = 0;
	while(p <= u)
	{
		nod = c[p];
		p ++;
		
		for(int i = 0; i < v[nod].size(); i ++)
			if(viz[v[nod][i]] == -1)
			{
				u ++;
				viz[v[nod][i]] = 0;
				c[u] = v[nod][i];
			}
	}
}

int main()
{
	int x, y, c = 0;
	f >> n >> m;
	while(f >> x >> y)
		v[x].push_back(y);
	
	for(int i = 1; i <= n; i ++)
		viz[i] = -1;
	for(int i = 1; i <= n; i ++)
		if(viz[i] == -1)
		{
			bfs(i);
			c ++;
		}
	g << c;
}