Union Find(DSU)

아래는 Path Compression + Union by Rank가 모두 적용된 C++ 기반의 완성형 Union-Find (DSU) 코드입니다:

#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    // 생성자: N개의 원소 초기화 (0부터 N-1)
    UnionFind(int N) : parent(N), rank(N, 0) {
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }

    // 경로 압축 (Path Compression)
    int Find(int x) {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    // 랭크 기준 병합 (Union by Rank)
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // 연결 여부 확인
    bool Connected(int x, int y) {
        return Find(x) == Find(y);
    }
};

✅ 특징 요약