Cod sursa(job #323860)

Utilizator John_the_BraveJohn Abruzzi John_the_Brave Data 13 iunie 2009 21:18:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<vector>
#define NMAX 100002
using namespace std;


vector< int > G[NMAX];
int C[NMAX];
int val;

void df(const int nod)
{
	vector< int >::iterator it;

	for( it=G[nod].begin(); it!=G[nod].end(); ++it ) 
		if( C[ *it ]!=val )
		{
			C[*it]=val;df(*it);
		}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int N,M;
	scanf("%d%d",&N,&M);

	int i,a1,a2;
	for(i=1; i<=M; ++i)
	{
		scanf("%d%d",&a1,&a2);
		G[a1].push_back(a2);
		G[a2].push_back(a1);
	}

	int ANS=N;
	for(i=1; i<=N; ++i)
		C[i]=i;

	for(i=1; i<=N; ++i)
		if( C[i]==i )
		{
			val=i;
			df(i);
		}
		else
			--ANS;

	printf("%d\n",ANS);

	return 0;
}