Cod sursa(job #372569)

Utilizator loginLogin Iustin Anca login Data 10 decembrie 2009 20:14:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
# include <fstream>
using namespace std;
int n, m, t[100003], nrc, h[100003];

int rad (int x)
{
	while (t[x]) x=t[x];
	return x;
}

void reuniune (int x, int y)
{
	int rx, ry;
	rx=rad(x);
	ry=rad(y);
	if (rx!=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 ()
{
	ifstream fin ("dfs.in");
	ofstream fout ("dfs.out");
	fin>>n>>m;
	nrc=n;
	for (;m;m--)
	{
		int i, j;
		fin>>i>>j;
		reuniune (i, j);
	}
	fout<<nrc;
	return 0;
}