Cod sursa(job #3192418)

Utilizator BurloiEmilAndreiBurloi Emil Andrei BurloiEmilAndrei Data 12 ianuarie 2024 16:00:20
Problema Paduri de multimi disjuncte Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

class DSU {
public:
    int rank[MAXN], parent[MAXN];

    void init () {
        int i;

        for (i = 1; i <= MAXN; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    int findParent (int node) {
        if (parent[node] == node) {
            return node;
        } else {
            return (parent[node] = findParent(parent[node]));
        }
    }

    void unite (int nod1, int nod2) {
        int parentNod1 = findParent(nod1);
        int parentNod2 = findParent(nod2);

        if (rank[parentNod1] < rank[parentNod2]) {
            swap(parentNod1, parentNod2);
        }

        rank[parentNod2] += rank[parentNod1];
        parent[nod2] = parent[nod1];
    }
};

DSU dsu;

int main()
{
    ifstream cin("disjoint.in");
    ofstream cout("disjoint.out");
    
    int n, m, i, tip, x, y;

    cin >> n >> m;

    dsu.init();
    for (i = 0; i < m; i++) {
        cin >> tip >> x >> y;

        if (tip == 1) {
            dsu.unite(x, y);
        } else {
            if (dsu.findParent(x) == dsu.findParent(y)) {
                cout << "DA\n";
            } else {
                cout << "NU\n";
            }
        }
    }
    return 0;
}