Cod sursa(job #577962)

Utilizator darkseekerBoaca Cosmin darkseeker Data 10 aprilie 2011 20:22:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <cstdio>
#define NMAX 100007
#define Input "dfs.in"
#define Output "dfs.out"
using namespace std;

int tata[NMAX],h[NMAX],N,M,nrc=0;

inline void uneste(int a,int b)
{
	if(h[a] > h[b])
		tata[b]=a;
	else
		tata[a]=b, h[b]+=(h[a]==h[b])?1:0;
}

inline int cauta(int a)
{
	int r=a,y=a,t;
	while(tata[r]) r=tata[r];
	while(y!=r)
	{
		t=tata[y];
		tata[y]=r;
		y=t;
	}
	return r;
}

int main(){
	ifstream fin(Input);
	freopen (Output,"w",stdout);
	
	int i,e1,e2,v1,v2;
	fin>>N>>M;
	
	for(i=1; i<=M; i++)
	{
		fin>>e1>>e2;
		v1=cauta(e1);
		v2=cauta(e2);
		if(v1 != v2)
			uneste(v1,v2);
	}
	
	for(i=1; i<=N; i++)
		if(tata[i] == 0)
			nrc++;
	
	printf("%d\n",nrc);
	return 0;
}