Cod sursa(job #764708)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 5 iulie 2012 23:07:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <iostream>

using namespace std;
const int maxn = 100010;

struct nod {
	int val;
	nod *urm ;
} *G[maxn];
int n, m, sol, viz[maxn];


void add(int x, int y) {
	nod *curr = new nod;
	curr -> urm = G[x];
	curr -> val = y;
	G[x] = curr;
}
void dfs(int node) {
	viz[node] = 1;
	
	for( nod *curr = G[node]; curr ; curr = curr -> urm) 
		if(!viz[ curr -> val] )
			dfs(curr -> val);
}	
int main() {
	
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	int a, b;
	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d\n", &a, &b);
		add(a, b); add(b, a);
	}
	
	for(int i = 1; i <= n; ++i)
		if(!viz[i])
			dfs(i), ++sol;
	
	printf("%d\n", sol);
	
	return 0;
}