Cod sursa(job #677475)

Utilizator Catah15Catalin Haidau Catah15 Data 10 februarie 2012 11:37:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

#define maxN 100005
#define PB push_back

vector <int> list[maxN];
int sol;
bool cont[maxN];


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


int main()
{
	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int a, b;
		
		scanf ("%d %d", &a, &b);
		
		list[a].PB (b);
		list[b].PB (a);
	}
	
	for (int i = 1; i <= N; ++ i) if (! cont[i]) dfs (i), ++ sol;
	
	printf ("%d", sol);
	
	return 0;
}