Cod sursa(job #923018)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 22 martie 2013 19:40:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<cstdio>
#include<vector>
#define Nmax 100001

using namespace std;

vector <int> a[Nmax];
int N,M,sol;
bool viz[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);
	}
	
	for(int i=1; i<=N; ++i)
		if(!viz[i]){
			++sol;
			dfs(i);
		}

	printf("%d",sol);
return 0;
}