Cod sursa(job #500549)

Utilizator vrvpcppveigang radulescu vlad petru vrvpcpp Data 12 noiembrie 2010 15:18:29
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
vector <int> l[100000];
int n,m,i,x,y,nr;
bool sel[100000];
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("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%ld %ld",&n,&m);
	for (i=1;i<=m;i++) {
		scanf("%ld %ld",&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("%ld\n",nr);
	return 0;
}