Cod sursa(job #500519)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 12 noiembrie 2010 15:02:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <string.h>

using namespace std;

vector <int> l[100001];
int n,m,i,j,x,y,nr;
bool sel[100001];

void df(int x) {
	vector <int> :: iterator it;
	sel[x]=true;
	for (it=l[x].begin(); it!=l[x].end(); it++) 
		if (!sel[*it]) {
			df(*it);
		}
}

int main () {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; i++) {
		scanf("%d%d",&x,&y);
		l[x].push_back(y);
		l[y].push_back(x);
	}
	memset(sel,false,sizeof(sel));
	nr=0;
	for (i=1; i<=n; i++) 
		if (!sel[i]) {
			nr++;
			df(i);
		}
	printf("%d\n",nr);
	return 0;
}