Cod sursa(job #2928093)
Utilizator | Data | 22 octombrie 2022 10:35:45 | |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.05 kb |
#include<iostream>
using namespace std;
const int NMAX = 1e5 + 1;
int t[NMAX],rang[NMAX];//t[i] = tatal lui i,daca t[i] = 0,i e fatherless
void unite(int a,int b)
{
t[a] = b;
}
int find(int a)
{
int root = a,c = a,cc;
while(t[root]) root = t[root];
while(c != root)
{
cc = c;
c = t[c];
t[cc] = root;
}
return root;
}
int main()
{
freopen("disjoint.in","r",stdin);
freopen("disjoint.out","w",stdout);
int n,q,a,b,t;
cin >> n >> q;
while(q--)
{
cin >> t >> a >> b;
if(t & 1)
{
unite(find(a),find(b));
}
else
{
if(find(a) == find(b) && find(a))
{
cout << "DA\n";
}
else
{
cout << "NU\n";
}
}
}
}