유니온 파인드

좋아! 유니온 파인드(Union-Find, 또는 Disjoint Set Union, DSU)는 서로소 집합(Disjoint Set)을 관리하는 자료구조야. 주로 네트워크 연결 여부 판단, 최소 스패닝 트리(Kruskal 알고리즘) 등에 자주 사용돼.

📌 유니온 파인드 개념 정리
핵심 기능 2가지:
Find(x)

원소 x가 속한 집합의 대표(root)를 찾는다.

경로 압축(Path Compression)을 통해 속도를 향상시킬 수 있음.

Union(x, y)

원소 x와 y가 속한 집합을 합친다.

보통 랭크(또는 크기)를 이용해 더 작은 집합을 큰 집합에 붙이는 최적화를 사용.

🧠 예: 친구 네트워크
1과 2가 친구라면 Union(1, 2)

2와 3이 친구라면 Union(2, 3)

그 후 Find(1) == Find(3) 이면 → 같은 집합 (서로 연결됨)

✅ C++ 예시 코드

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1); // 집합의 크기

        for (int i = 0; i < n; ++i)
            parent[i] = i; // 자기 자신이 부모
    }

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

    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 {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY])
                rank[rootX]++;
        }
    }

    bool Connected(int x, int y) {
        return Find(x) == Find(y);
    }
};

// 사용 예시
int main() {
    UnionFind uf(10);

    uf.Union(1, 2);
    uf.Union(2, 3);
    uf.Union(4, 5);

    std::cout << std::boolalpha;
    std::cout << "1과 3은 연결되어 있는가? " << uf.Connected(1, 3) << '\n';
    std::cout << "1과 5는 연결되어 있는가? " << uf.Connected(1, 5) << '\n';

    uf.Union(3, 5);

    std::cout << "1과 5는 이제 연결되어 있는가? " << uf.Connected(1, 5) << '\n';

    return 0;
}