Cod sursa(job #372563)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 10 decembrie 2009 20:06:08
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.44 kb
using namespace std;
#include<fstream>
int n,m,nrc,t[100000];
int radacina(int x)
{
	while(t[x])x=t[x];
	return x;
}
void reuniune(int x,int y)
{
	if(radacina(x)!=radacina(y))
	{
		t[x]=radacina(y);
		nrc--;
	}
}
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;
}