Pagini recente » Cod sursa (job #1844851) | Cod sursa (job #2406776) | Cod sursa (job #640631) | Cod sursa (job #1460749) | Cod sursa (job #1770632)
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, t[100005], in[100005];
void citire()
{
scanf("%d %d", &n, &m);
for(int i=1; i<=n; ++i)
{
t[i]=i;
in[i]=1;
}
}
int radacina(int x)
{
while(x!=t[x])
{
x=t[x];
}
return x;
}
void compresie(int x, int y)
{
int radx=radacina(x);
int rady=radacina(y);
while(y!=rady)
{
int aux=t[y];
t[y]=radx;
y=aux;
}
t[y]=radx;
}
void reunireMultimi(int x, int y)
{
int radx=radacina(x);
int rady=radacina(y);
if(in[radx]>=in[rady])
{
compresie(x, y);
in[radx]=max(in[radx], in[rady]+1);
in[rady]=in[radx];
}
else
{
compresie(y, x);
in[rady]=max(in[rady], in[radx]+1);
in[radx]=in[rady];
}
}
int verificareMultime(int x, int y)
{
if(radacina(x)==radacina(y))
return 1;
return 0;
}
void rezolvare()
{
int cod, x, y;
for(int i=1; i<=m; ++i)
{
scanf("%d %d %d", &cod, &x, &y);
if(cod==1)
{
reunireMultimi(x, y);
}
else
{
if(verificareMultime(x, y))
printf("DA\n");
else
printf("NU\n");
}
}
}
int main()
{
freopen("disjoint.in", "r", stdin);
freopen("disjoint.out", "w", stdout);
citire();
rezolvare();
return 0;
}