Cod sursa(job #811559)

Utilizator ephgstefana gal ephg Data 12 noiembrie 2012 17:28:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
#define BM 100005
typedef vector<int>::iterator it;
vector<int>g[BM];
int n,m,c;
bitset <BM> viz;
void dfs(int i){
	for(it ii=g[i].begin();ii!=g[i].end();++ii)if(!viz[*ii]){
		viz[*ii]=1;
		dfs(*ii);
	}
}
int main () {
	int i,a,b;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d %d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(i=1;i<=n;++i)if(!viz[i]){
		++c;
		dfs(i);
	}
	printf("%d",c);
	return 0;
}