Cod sursa(job #3192570)
Utilizator | Bianca Lautaru biancalautaru | Data | 12 ianuarie 2024 21:43:07 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.74 kb |
#include <fstream>
#define DIM 100001
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int n,q,op,x,y,t[DIM];
int root(int x) {
while (t[x]>0)
x=t[x];
return x;
}
int main() {
fin>>n>>q;
for (int i=1;i<=n;i++)
t[i]=-1;
while (q--) {
fin>>op>>x>>y;
int rx=root(x);
int ry=root(y);
if (op==1)
if (-t[rx]>-t[ry]) {
t[rx]+=t[ry];
t[ry]=rx;
}
else {
t[ry]+=t[rx];
t[rx]=ry;
}
else
if (rx==ry)
fout<<"DA\n";
else
fout<<"NU\n";
}
return 0;
}