Cod sursa(job #3375053)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 10 noiembrie 2026 03:01:22
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
using namespace std;

vector<int> p, r;

int find(int x) {
    while (p[x] != x) {
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (r[a] < r[b]) swap(a, b);
    p[b] = a;
    if (r[a] == r[b]) r[a]++;
}

int main() {
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");
    int n, m;
    fin >> n >> m;
    p.resize(n + 1);
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) p[i] = i;
    while (m--) {
        int c, x, y;
        fin >> c >> x >> y;
        if (c == 1) unite(x, y);
        else fout << (find(x) == find(y) ? "DA" : "NU") << '\n';
    }
    return 0;
}