Cod sursa(job #372492)

Utilizator titusuTitus C titusu Data 10 decembrie 2009 16:06:42
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
/*
 * paduri de multimi disjuncte
 * */
#include <fstream>
#define NMAX 100001
using namespace std;

int tata[NMAX], h[NMAX], n, nrc;

int root(int x){
	int y=x,tmp;
	while(tata[y])
		y=tata[y];
	while(tata[x]){
		tmp=x;
		x=tata[x];
		tata[tmp]=y;
	}
	return y;
}

int main(){
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int m,i,j,ri,rj;
	fin>>n>>m;
	nrc=n;
	for( ; m ;--m){
		fin>>i>>j;
		ri=root(i);
		rj=root(j);
		if(ri != rj){
			if(h[i]>h[j])
				tata[j]=i;
			else
				if(h[i] < h[j])
					tata[i] = j;
				else{
					tata[i]=j;
					h[i]++;
				}
			nrc--;
		}
	}
	fout<<nrc;
	return 0;
}