Cod sursa(job #230478)
Utilizator | Damaschin Mihai dama | Data | 14 decembrie 2008 00:50:54 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.88 kb |
#include <stdio.h>
int r[100001], n, m;
int f(int);
int main()
{
freopen("disjoint.in", "r", stdin);
freopen("disjoint.out", "w", stdout);
int i, tip, a, b;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; ++i)
{
r[i] = i;
}
for(i = 1; i <= m; ++i)
{
scanf("%d %d %d", &tip, &a, &b);
if(tip == 1)
{
if(a < b)
{
r[b] = a;
}
else
{
r[a] = b;
}
}
else
{
if(f(a) == f(b))
{
printf("DA\n");
}
else
{
printf("NU\n");
}
}
}
return 0;
}
int f(int a)
{
if(r[a] != r[r[a]])
{
r[a] = f(r[a]);
}
return r[a];
}