Cod sursa(job #680481)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 15 februarie 2012 17:52:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
#include<vector>
#define Nmax 100010

using namespace std;

int N,M,nr;
bool viz[Nmax];

vector <int> a[Nmax];

void df(int nod){
	
	viz[nod]=1;
	
	for(vector <int>::iterator it=a[nod].begin(); it!=a[nod].end(); ++it)
		if(!viz[*it])
			df(*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);
	}
	
	for(int i=1;i<=N;++i)
		if(!viz[i])
			++nr,
			df(i);
	
	printf("%d",nr);
	
return 0;
}