Cod sursa(job #2946474)
Utilizator | Iordache Ana-Georgiana Iordache_Ana | Data | 24 noiembrie 2022 21:36:20 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int v[100005],n,m,op,a,b,i;
int rad(int a)
{
if(v[a]==0)
return a;
v[a]=rad(v[a]);
return v[a];
}
void reun(int a, int b)
{
int ra,rb;
ra=rad(a);
rb=rad(b);
if(a>b)
v[ra]=rb;
else
v[rb]=ra;
}
int main()
{
f>>n>>m;
for(i=0; i<m; i++)
{
f>>op>>a>>b;
if(op==1)
reun(a,b);
else if(rad(a)==rad(b))
g<<"DA"<<"\n";
else
g<<"NU"<<"\n";
}
f.close();
g.close();
return 0;
}