Cod sursa(job #372570)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 10 decembrie 2009 20:14:32
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
using namespace std;
#include<fstream>
int n,m,nrc,t[100000],h[100000];
int radacina(int x)
{
	while(t[x])x=t[x];
	return x;
}
void reuniune(int x,int y)
{
	int rx=radacina(x);
	int ry=radacina(y);
	if(rx!=ry)
	{
		t[x]=ry;
		nrc--;
		if(h[rx]>h[ry])
			t[ry]=rx;
		else
			if(h[rx]<h[ry])
				t[rx]=ry;
		else
		{
			t[rx]=ry;
			h[ry]++;
		}
	}
}
int main()
{
	int i,x,y;
	ifstream fin("dfs.in");
	fin>>n>>m;
	nrc=n;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		reuniune(x,y);
	}
	fin.close();
	ofstream fout("dfs.out");
	fout<<nrc;
	fout.close();
	return 0;
}