Cod sursa(job #2670407)
Utilizator | Tudor Pasca Tudor_Pasca | Data | 9 noiembrie 2020 20:43:57 |
---|---|---|---|
Problema | Paduri de multimi disjuncte | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("disjoint.in");
ofstream out("disjoint.out");
int n, t;
int father[100100], depth[100100];
int root(int node)
{
int x = node;
while(father[x] != 0)
x = father[x];
return x;
}
void connect(int x, int y)
{
father[x] = y;
}
int main()
{
in >> n >> t;
while(t--)
{
int q, x, y;
in >> q >> x >> y;
if(q == 1)
connect(root(x), root(y));
else
out << (root(x) == root(y) ? "DA\n" : "NU\n");
}
return 0;
}