Pagini recente » Cod sursa (job #3184499) | Cod sursa (job #994784) | Cod sursa (job #1586767)
#include <fstream>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int tata[100001];
void uneste(int a,int b)
{
while(a!=tata[a]) a=tata[a];
while(b!=tata[b]) b=tata[b];
tata[a]=b;
}
int cauta(int a,int b)
{
int aux;
int x=a;
while(a!=tata[a]) a=tata[a];
while(x!=tata[x])
{
aux=x;
x=tata[x];
tata[aux]=a;
}
x=b;
while(b!=tata[b]) b=tata[b];
while(x!=tata[x])
{
aux=x;
x=tata[x];
tata[aux]=b;
}
if(a==b) return 1;
else return 0;
}
int main()
{
int n,m,i,a,b,c,ok;
f>>n>>m;
for(i=1;i<=n;i++) tata[i]=i;
for(i=1;i<=m;i++)
{
f>>a>>b>>c;
if(a==1)
{
uneste(b,c);
}
else
{
ok=cauta(b,c);
if(ok==0) g<<"NU\n";
else g<<"DA\n";
}
}
}