Cod sursa(job #151892)

Utilizator devilkindSavin Tiberiu devilkind Data 8 martie 2008 18:52:07
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 100000
#define pb push_back
#define sz size()


vector<int> G[NMAX];
long int viz[NMAX];
long int n,k;

void DFS(long int nod)
{
	viz[nod]=1;
	long int i;
	for (i=0;i<G[nod].sz;i++)
		if (!viz[ G[nod][i] ]) DFS(G[nod][i]);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	long int i,m,x,y;

	scanf("%ld %ld",&n,&m);
	
	for (i=1;i<=m;i++)
		{
			scanf("%ld %ld",&x,&y);
			G[x].pb(y);
			G[y].pb(x);
		}

	for (i=1;i<=n;i++)
		if (!viz[i])
		{
			++k;
			DFS(i);
		}
	printf("%ld",k);
	return 0;
}