Cod sursa(job #666985)

Utilizator federerUAIC-Padurariu-Cristian federer Data 22 ianuarie 2012 15:04:06
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <vector>
using namespace std;

#define MAXN 100100

int N, M, nrcon;
vector<int> G[MAXN];
int viz[MAXN];

void dfs(int x)
{
	viz[x] = 1;
	for(int i = 0; i < G[x].size(); i++)
		if(!viz[G[x][i]])
			dfs(G[x][i]);
}

int main(void)
{
	freopen("dfs.in", "rt", stdin);
	freopen("dfs.out", "wt", stdout);
	
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i = 1; i <= N; i++)
	{
		if(!viz[i])
			nrcon++, dfs(i);
	}
	printf("%d\n", nrcon);
	fclose(stdin);
	fclose(stdout);
	return 0;
}