Cod sursa(job #651092)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 19 decembrie 2011 19:41:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<cstdio>
#include<vector>
#define NMAX 100400 
using namespace std;
int x,y,n,m,viz[NMAX],ne,i,j,fiu,nd;
vector <int> G[NMAX];
void dfs(int k){
	viz[k]=1;
	for(size_t i=0; i<G[k].size();++i){
		if(!viz[G[k][i]]){
			dfs(G[k][i]);
		}
	}
}
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);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	ne=0;
	for(i=1;i<=n;++i){
		if(!viz[i]){
			dfs(i);
			++ne;
		}
	}
	printf("%d",ne);
	return 0;
}