Cod sursa(job #943509)
#include <fstream>
#include <cstdlib>
using namespace std;
const int NMAX = 100011;
int N;
int f[NMAX], rank[NMAX];
int find(int x)
{
int y, z;
for(y = x; y != f[y]; y = f[y]);
while(x != f[x])
{
z = f[x];
f[x] = y;
x = z;
}
return y;
}
void Union(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx == fy) return;
if(rank[fx] > rank[fy])
{
f[fx] = fy;
rank[fy] += rank[fx];
}
else {
f[fy] = fx;
rank[fx] += rank[fy];
}
}
int main()
{
int N, M, op, x, y;
ifstream in("disjoint.in");
ofstream out("disjoint.out");
in >> N >> M;
for(int i = 1; i <= N; ++i)
{
f[i] = i;
rank[i] = 1;
}
for(; M; --M)
{
in >> op >> x >> y;
if(1 == op)
{
Union(x, y);
}
else out << (find(x) == find(y) ? "DA" : "NU") << '\n';
}
return EXIT_SUCCESS;
}