Cod sursa(job #560297)

Utilizator Catah15Catalin Haidau Catah15 Data 18 martie 2011 13:44:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>

using namespace std;

#define maxN 100005
#define PB push_back


int sol, N, M;
vector < int > lista[maxN];
bool cont[maxN];


void vecini (int nod)
{
	cont[nod] = true;
	
	for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		if ( ! cont[lista[nod][i]] )
			vecini ( lista[nod][i] );
}


int main()
{
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	
	f >> N >> M;
	
	for (int i = 1; i <= M; ++ i)
	{
		int x, y;
		
		f >> x >> y;
		
		lista[x].PB(y);
		lista[y].PB(x);
	}
	
	for (int i = 1; i <= N; ++ i)
	{
		if ( cont[i] )
			continue;
		
		cont[i] = true;
		
		for (unsigned int j = 0; j < lista[i].size(); ++ j)
			if ( ! cont[lista[i][j]] )
				vecini (lista[i][j]);
			
		++ sol;
	}
	
	g << sol;
	
	return 0;
}