Cod sursa(job #701103)

Utilizator RengelBotocan Bogdan Rengel Data 1 martie 2012 13:38:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstdio>
#include<vector>

#define L 100005

int F[L];
std :: vector <int> A[L];
std :: vector <int> :: iterator it;

int N,M;

void read(){
	
	scanf("%d%d",&N,&M);
	
	int x,y;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&x,&y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	
}

void df(int nod){
	
	F[nod]++;
	
	std :: vector <int> :: iterator it;
	for(it = A[nod].begin(); it < A[nod].end(); it++)
		if(!F[*it])
			df(*it);
	
}

void solve(){
	
	int componente = 0;
	
	for(int i = 1; i <= N; i++)
		if(!F[i]){
			df(i);
			componente++;
		}
	
	printf("%d",componente);
	
}

int main(){
	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	read();
	solve();
	
	return 0;
	
}