Cod sursa(job #579126)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 11 aprilie 2011 21:13:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<cstdio>
#include<vector>
#define Nmax 100010

using namespace std;

int N,M;
bool viz[Nmax];

vector <int> a[Nmax];

void dfs(int nod){
	
	viz[nod]=1;
	
	for(vector <int>::iterator it = a[nod].begin(); it!=a[nod].end(); ++it)
		if(!viz[*it])
			dfs(*it);
}

int main(){
	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=M;++i){
		
		int x,y;
		scanf("%d%d",&x,&y);
		
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	int sol=0;
	for(int i=1;i<=N;++i)
		if(!viz[i])
			sol++,
			dfs(i);
			
	printf("%d\n",sol);
	
return 0;
}