[C++] Disjoint Set 기초 구현

이건 솔직히 너무 쉬워서 뭐 설명할 게 없음

 

class DisjointSet {
    std::vector<int> parent;
public:
    explicit    DisjointSet(int n);
    int         get_parent(int idx);
    bool        join(int i, int j);
    bool        _joined_(int i, int j);
};

DisjointSet::DisjointSet(int n) : parent(n) {
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

int DisjointSet::get_parent(int idx) {
    if (idx == parent[idx]) {
        return idx;
    } return parent[idx] = get_parent(parent[idx]);
}

bool DisjointSet::join(int i, int j) {
    int pi = get_parent(i), pj = get_parent(j);
    if (pi == pj) {
        return false;
    } else {
        parent[pj] = pi;
        return true;
    }
}

bool DisjointSet::_joined_(int i, int j) {
    int pi = get_parent(i), pj = get_parent(j);
    return pi == pj;
}