Cod sursa(job #362173)

Utilizator tranbachhaiTran Bach Hai tranbachhai Data 8 noiembrie 2009 12:32:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<stdio.h>
#include<vector>
#define NMAX 100010
using namespace std;
long n,m,nr,viz[NMAX];
vector<long> list[NMAX];

void dfs(long nod)
{
	viz[nod]=1;
	long i;
	for(i=0;i<list[nod].size();++i)
		if(!viz[list[nod][i]])
			dfs(list[nod][i]);
}

int main()
{
long i,x,y;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=m;++i)
{
	scanf("%ld%ld",&x,&y);
	list[x].push_back(y);
	list[y].push_back(x);
}
for(i=1;i<=n;++i)
	if(viz[i]!=1)
	{
		++nr;
		dfs(i);
	}
	printf("%ld",nr);
return 0;
}