Cod sursa(job #916571)

Utilizator EduardGeorgescuGeorgescu Eduard EduardGeorgescu Data 16 martie 2013 17:50:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<cstdio>
#include<vector>

using namespace std;

vector <int> Graf[100010];
char v[100010];

void dfs(int x){	
		
	v[x]=1;
	
	vector <int> ::iterator it ;
	
	for( it = Graf[x].begin() ; it != Graf[x].end() ; it ++ )
		if(v[*it]==0)
			dfs(*it);
		
}

int main(){
	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int N,M;
	
	scanf("%d%d" , &N , &M);
	
	int i,nod1,nod2;
	
	for ( i = 1 ; i <= M ; i ++){
		scanf("%d%d" , &nod1 , &nod2);
		Graf[nod1].push_back(nod2);
		Graf[nod2].push_back(nod1);
	}
	
	int nr=0;
	
	for ( i = 1 ; i <= N ; i ++)
		if(!v[i]){
			++nr;
			dfs(i);
		}
		
	printf("%d" , nr);
	
	return 0;
}