Cod sursa(job #372562)

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

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

void reuniune (int x, int y)
{
	int a, b;
	a=rad(x);
	b=rad(y);
	if (a!=b)
	{
		t[x]=b;
		nrc--;
	}
}

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;
}