Pagini recente » Cod sursa (job #91623) | Cod sursa (job #1988147) | Cod sursa (job #419094) | Cod sursa (job #3271408) | Cod sursa (job #420471)
Cod sursa(job #420471)
#include <stdio.h>
#define NMAX 100001
long a, b, code, n, m, rang[NMAX], p[NMAX];
long find(long x)
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
void add(long x)
{
p[x] = x;
rang[x] = 0;
}
void join (long x, long y)
{
if (rang[x] > rang[y])
p[y] = x;
else
{
p[x] = y;
if (rang[y] == rang[x])
++rang[y];
}
}
void rejoin(long x, long y)
{
join(find(x), find(y));
}
int main()
{
freopen ("disjoint.in", "rt", stdin);
freopen ("disjoint.out", "wt", stdout);
scanf("%ld %ld", &n, &m);
for (long i = 1; i <= n; ++i)
add(i);
for (long i = 1; i <= m; ++i)
{
scanf("%ld", &code);
if (code == 1)
{
scanf("%ld %ld", &a, &b);
rejoin(a, b);
}
else
{
scanf("%ld %ld", &a, &b);
if (p[find(a)] == p[find(b)])
printf("DA\n");
else
printf("NU\n");
}
}
return 0;
}