Cod sursa(job #2859023)
Utilizator | Leoveanu Bianca Biencutza04 | Data | 28 februarie 2022 19:04:14 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <fstream>
using namespace std;
ifstream f("disjoint.in"); ofstream g("disjoint.out");
int n,m,T[100001];
int Radacina(int x)
{ int R,y;
for(R=x;T[R]!=R;R=T[R]);
for(;T[x]!=x;) {y=T[x]; T[x]=R; x=y;}
return R;
}
void Unire(int k, int p)
{ T[k]=p;}
int main()
{ f>>n>>m;
for(int i=1;i<=n;i++) T[i]=i;
while(m--)
{ int x,y,op;
f>>op>>x>>y;
if(op==1) Unire(Radacina(x),Radacina(y));
else
if(Radacina(x)==Radacina(y)) g<<"DA\n";
else g<<"NU\n";
}
g.close(); f.close(); return 0;
}