Pagini recente » Cod sursa (job #208386) | Cod sursa (job #436668) | Cod sursa (job #1065832) | Cod sursa (job #436808) | Cod sursa (job #1756804)
#include <iostream>
#include <fstream>
using namespace std;
#define NMAX 100001
struct Nod
{
int tata;
int rang = 1;
};
Nod noduri[NMAX];
bool inAcelasiArbore(int x, int y);
void reuneste(int x, int y);
int radacina(int x);
int main()
{
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int n, m;
fin >> n >> m;
while (m--) {
int r, x, y;
fin >> r >> x >> y;
if (r == 1) {
reuneste(x, y);
}
else {
fout << ((inAcelasiArbore(x, y)) ? "DA" : "NU") << "\n";
}
}
return 0;
}
bool inAcelasiArbore(int x, int y)
{
int rx = radacina(x);
int ry = radacina(y);
while (x != rx) {
int cx = x;
x = noduri[x].tata;
noduri[cx].tata = rx;
}
return rx == ry;
}
void reuneste(int x, int y)
{
int rx = radacina(x);
int ry = radacina(y);
if (noduri[rx].rang > noduri[ry].rang) {
swap(rx, ry);
}
noduri[ry].tata = rx;
noduri[rx].rang += noduri[ry].rang;
}
int radacina(int x)
{
while (noduri[x].tata != 0) {
x = noduri[x].tata;
}
return x;
}