Cod sursa(job #1404187)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 27 martie 2015 21:18:46
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
using namespace std;

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
const int kMax = 1e5 + 5;
int n, m, TT[kMax], rnk[kMax];

int find(int x)
{
	int anc;
	for (anc = x; anc != TT[anc]; anc = TT[anc]);

	while (x != anc)
	{
		int aux = TT[x];
		TT[x] = anc;
        x = aux;
	}
	return anc;
}

void unite(int x, int y)
{
	x = find(x);	y = find(y);
	if (rnk[y] > rnk[x])
		swap(x, y);

	TT[y] = x;
    ++rnk[x];
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		TT[i] = i;
		rnk[i] = 1;
	}

	while (m--)
	{
        int opt, x, y;
        fin >> opt >> x >> y;
        if (opt == 1)
			unite(x, y);
		else
            fout << (find(x) == find(y) ? "DA" : "NU") << '\n';
	}
	return 0;
}