Pagini recente » Cod sursa (job #2140484) | Cod sursa (job #1012274) | Borderou de evaluare (job #254354) | Cod sursa (job #1017130) | Cod sursa (job #3002168)
#include <bits/stdc++.h>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int rang[100001],tata[100001];
int radacina(int x)
{
int aux,r;
aux=x;
while(tata[x]!=0)
{
x=tata[x];
}
r=x;
x=aux;
while(tata[x]!=0)
{
aux=tata[x];
tata[x]=r;
x=aux;
}
return r;
}
void unire(int x,int y)
{
x=radacina(x);
y=radacina(y);
if(rang[x]>=rang[y])
{
tata[y]=x;
rang[x]++;
}
else
{
tata[x]=y;
rang[y]++;
}
}
int main()
{int n,m,i,op,x,y;
f>>n>>m;
for(i=1;i<=n;i++)
{
rang[i]=1;
}
for(i=1;i<=m;i++)
{
f>>op>>x>>y;
if(op==1)
{
unire(x,y);
}
else
{
x=radacina(x);
y=radacina(y);
if(x==y)
{
g<<"DA"<<'\n';
}
else
{
g<<"NU"<<'\n';
}
}
}
return 0;
}