Pagini recente » Cod sursa (job #1549081) | Cod sursa (job #2076735) | Istoria paginii runda/infoexpet | Cod sursa (job #1121785) | Cod sursa (job #2292666)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("disjoint.in");
ofstream fout ("disjoint.out");
int t[100005],rang[100005];
int findroot(int x)
{
int root=t[x];
while(root!=t[root])
{
root=t[root];
}
while (t[x]!=x)
{
int aux=t[x];
t[x]=root;
x=aux;
}
return root;
}
void reuniune(int x,int y)
{
if (rang[y]<rang[x])
t[findroot(x)]=findroot(y);
else
t[findroot(y)]=findroot(x);
if (rang[y]==rang[x])
rang[y]++;
}
int main()
{
int n,m;
fin>>n>>m;
for (int i=1;i<=n;i++)
{
t[i]=i;
rang[i]=1;
}
for (int var=0;var<m;var++)
{
char cer;
int x,y;
fin>>cer>>x>>y;
if (cer=='1')
{
reuniune(x,y);
}
else
{
if (findroot(x)==findroot(y))
fout<<"DA\n";
else
fout<<"NU\n";
}
}
return 0;
}