Pagini recente » Cod sursa (job #1606464) | Profil timofte24 | Cod sursa (job #2457017)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int rnk[100005],dad[100005];
int n,m,cod,x,y;
int root(int nod)
{
int nodinit=nod, x=dad[nod];
while(nod!=x)
{
nod=x;
x=dad[nod];
}
dad[nodinit]=x;
return x;
}
void join(int x,int y)
{
x=root(x);
y=root(y);
if(rnk[x]>rnk[y])
dad[y]=x;
else
if(rnk[y]>rnk[x])
dad[x]=y;
else
rnk[y]++,dad[x]=y;
}
int main()
{
int i;
fin>>n>>m;
for(i=1;i<=n;i++)
dad[i]=i;
for(i=1;i<=m;i++)
{
fin>>cod>>x>>y;
if(cod==1)
join(x,y);
else
{
if(root(x)==root(y))
fout<<"DA"<<'\n';
else
fout<<"NU"<<'\n';
}
}
return 0;
}