Cod sursa(job #1075746)

Utilizator danny794Dan Danaila danny794 Data 9 ianuarie 2014 15:29:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 100005;
int N, M, count;
vector<int> edges[NMAX];
bool comp[NMAX];

void read() {
	freopen( "dfs.in", "r", stdin );
	freopen( "dfs.out", "w", stdout );
	scanf("%i %i", &N, &M);
	int from, to;
	for( int i = 0; i < M; i++) {
		scanf("%i%i", &from, &to);
		edges[from].push_back(to);
		edges[to].push_back(from);
	}
}

void dfs(int index) {
	comp[index] = 1;
	for(int i = 0; i < (int) edges[index].size(); i++)
		if( !comp[edges[index][i]] )
			dfs(edges[index][i]);
}

void solve() {
	for(int i = 1; i <= N; i++)
		if( !comp[i] ) {
			count++;
			dfs(i);
		}
}

int main() {
	read();
	solve();
	printf("%i", count);
	return 0;
}