Cod sursa(job #833307)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 decembrie 2012 11:26:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;
#define maxn 100100

vector <int> vec[maxn];
int N, M;
int sel[maxn];

int df(int nod) {
	
	sel[nod] = 1;
	for( size_t i = 0; i < vec[nod].size(); ++i) {
		if( sel[ vec[nod][i]] == 1) continue;
		df(vec[nod][i]);
	}
	return 1;
		
	
}

int main() {
	
	scanf("%d %d", &N, &M);
	
	for( int i = 1; i <= M; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	
	int nr = 0;
	for( int i = 1; i <= N; ++i) {
		if( sel[i] == 0) 
			df(i), nr++;;
	}
	
	cout<<nr;
	
	
	
	return 0;
}