Cod sursa(job #3209979)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 4 martie 2024 10:47:40
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#define ll long long
#define nl '\n'
#define FOR(i, a, b) for (int i = a; i <= b; ++i) 
#define F0R(i, a, b) for (int i = a; i >= b; --i)
#define FORd(i, n) for (int i = 0; i < n; ++i)
#define F0Rd(i, n) for (int i = n - 1; i >= 0; --i)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");

vector<int> size;
vector<int> root;

int get_root(int x) {
    int cx = x;
    while (cx != root[cx]) {
        cx = root[cx];
    }

    while (x != cx) {
        int y = x;
        x = root[x];
        root[y] = cx;
    }

    return x;
}

void unite(int root1, int root2) {
    if (size[root1] > size[root2]) {
        root[root2] = root1;
        size[root1] += size[root2];
    } else {
        root[root1] = root2;
        size[root2] += size[root1];
    }
}

void solve() {
    int n, m;
    fin >> n >> m;

    size.resize(n + 1);
    root.resize(n + 1);

    FOR(i, 0, n) {
        root[i] = i;
        size[i] = 1;
    }
    
    while (m--) {
        int op, x, y;
        fin >> op >> x >> y;
        if (op == 1) {
            unite(get_root(x), get_root(y));
        } else {
            fout << (get_root(x) == get_root(y) ? "DA" : "NU") << nl;
        }
    }
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}