[알고리즘/그래프] 유니온 파인드 (Union Find)

Union-Find 알고리즘은 서로소 집합을 효율적으로 표현하고 관리하는 자료구조입니다.

주로 그래프에서 사이클 판별, 크루스칼 알고리즘을 이용한 최소 신장 트리(MST) 구성 등에 사용됩니다.

 

 

 

Union-Find는 두 가지 주요 연산을 지원합니다:

find(x)	원소 x가 속한 집합의 대표(root 또는 부모)를 찾습니다.
union(x, y)	원소 x, y가 속한 두 집합을 하나로 합칩니다.

 

각 원소는 트리 구조로 연결되며, 각 집합은 하나의 루트 노드(대표 원소)를 가집니다.

 

 

예시

10개의 원소 (0 ~ 9)가 각각 독립적인 집합에 있는 상태

 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

i	0	1	2	3	4	5	6	7	8	9
parent	0	1	2	3	4	5	6	7	8	9

---

 union(1, 2) 실행

1 → 2

[0] [1→2] [3] [4] [5] [6] [7] [8] [9]

 

i	0	1	2	3	4	5	6	7	8	9
parent	0	1	1	3	4	5	6	7	8	9

---

 union(2, 5) 실행 (2와 5를 연결 → 사실상 1과 5를 연결)

 

1 → 2 → 5

 

[0] [1→2→5] [3] [4] [6] [7] [8] [9]

 

i	0	1	2	3	4	5	6	7	8	9
parent	0	1	1	3	4	1	6	7	8	9

---

 find(5) 실행

→ 결과: 1 (대표 원소)

i	0	1	2	3	4	5	6	7	8	9
parent	0	1	1	3	4	1	6	7	8	9

 

 

 

find, union 함수 구현 코드입니다.

std::vector<int>parent(n);

int find(int a) {
    return a == parent[a] ? a : parent[a] = find(parent[a]);
}

void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}