Union-Find: 연결하고 대표를 찾기

BFS/DFS는 이미 주어진 그래프를 탐색합니다. 이번에는 연결이 하나씩 추가될 때마다 두 원소가 같은 그룹인지 묻습니다. 부모 배열과 집합의 대표를 함께 보면, 경로 압축이 연결 관계를 바꾸는 연산이 아니라 조회를 빠르게 만드는 연산임을 확인할 수 있습니다.

Union-Find는 여러 원소를 서로 겹치지 않는 집합들로 나누어 관리하는 자료구조입니다. Disjoint Set Union, 줄여서 DSU라고도 부릅니다.

이 자료구조가 다루는 핵심 질문은 두 가지입니다.

1. x와 y는 지금 같은 집합에 있는가?
2. x가 속한 집합과 y가 속한 집합을 하나로 합칠 수 있는가?

연결 관계가 계속 추가되고, 중간중간 같은 그룹인지 확인해야 하는 문제라면 Union-Find를 먼저 떠올릴 만합니다. 대표적인 예시는 연결 요소 구하기, 사이클 판정, Kruskal 최소 신장 트리, 모임이나 관계 기록으로 그룹 묶기입니다.

원문 그림: Union-Find의 핵심 연산 크게 보기

집합을 숲으로 표현하기

Union-Find는 각 집합을 하나의 트리로 표현합니다. 트리의 루트가 그 집합의 대표입니다. 각 원소는 자기 부모를 하나만 기억합니다.

처음에는 모든 원소가 자기 자신만 들어 있는 집합입니다.

parent[0] = 0
parent[1] = 1
parent[2] = 2
parent[3] = 3

두 집합을 합칠 때는 한 집합의 대표를 다른 집합의 대표 밑에 붙입니다. 그래서 전체 구조는 여러 트리로 이루어진 숲이 됩니다.

0 <- 1 <- 3
2 <- 4
5

이 상태에서 0, 1, 3은 같은 집합이고, 2, 4는 다른 집합입니다. 원소 5는 혼자 있는 집합입니다.

find: 대표 찾기

가장 단순한 find는 부모를 계속 따라 올라가다가, 자기 자신을 부모로 가진 루트를 만나면 그 값을 반환합니다.

이 방식은 맞지만, 트리가 한 줄로 길게 늘어지면 한 번의 find가 O(n)까지 느려질 수 있습니다.

0 <- 1 <- 2 <- 3 <- 4 <- 5

find(5)는 5, 4, 3, 2, 1, 0을 모두 지나야 합니다. 이런 모양이 반복되면 Union-Find의 장점이 사라집니다.

경로 압축

경로 압축은 find를 하면서 지나간 원소들의 부모를 곧바로 대표로 바꾸는 최적화입니다.

처음 find(5)는 여러 노드를 지나갈 수 있습니다. 하지만 그 뒤에는 5의 부모가 바로 대표가 되므로 다음 조회가 훨씬 빨라집니다.

원문 그림: 경로 압축 전후 크게 보기

경로 압축은 답을 바꾸지 않습니다. 같은 집합 안에서 루트로 가는 길을 짧게 만드는 것뿐입니다.

union: 대표끼리 합치기

두 원소 a, b를 합칠 때는 반드시 먼저 대표를 찾아야 합니다.

a를 b 밑에 바로 붙이면 안 됩니다. a와 b가 집합의 중간 노드일 수도 있기 때문입니다. 항상 대표끼리 연결해야 집합 구조가 깨지지 않습니다.

크기 기준 합치기

단순히 한쪽 대표를 다른 쪽 대표 밑에 붙이면 트리가 길어질 수 있습니다. 그래서 각 집합의 크기를 size[root]에 저장하고, 작은 집합을 큰 집합 밑에 붙입니다.

이때 size 값은 대표에서만 의미가 있습니다. rootB가 rootA 밑으로 들어간 뒤에는 size[rootB]를 참조하면 안 됩니다.

원문 그림: 크기 기준 합치기 크게 보기

비슷한 최적화로 rank 기준 합치기도 있습니다. rank는 트리 높이의 대략적인 상한을 저장합니다. 실전에서는 크기 기준 합치기가 이해하기 쉽고, 집합 크기까지 같이 필요한 경우가 많아 자주 쓰입니다.

부모를 바꾸어도 같은 집합입니다

그림 크게 보기 · 부모 배열과 집합을 움직이는 실험

원소가 6개일 때 unite(0,1), unite(2,3), unite(0,2)를 수행하면 {0,1,2,3}, {4}, {5}의 세 집합이 됩니다. 같은 크기에서는 첫 인자의 대표 아래로 합치는 원본 구현을 따릅니다. 부모 배열은 [0,0,0,2,4,5]입니다.

이어서 componentSize(3)을 호출하면 3 → 2 → 0을 따라가고, 돌아오면서 parent[3] = 0으로 압축합니다. 부모 배열은 [0,0,0,0,4,5]로 바뀌지만 집합과 크기 4는 같습니다. 대표 번호는 집합을 식별할 뿐 최솟값이라는 보장이 없습니다.

unite(1,3)은 두 대표가 모두 0이어서 false입니다. 성공한 병합만 집합 수를 하나 줄입니다. 실험의 size 행은 대표에서만 값을 보여 줍니다. 합쳐진 옛 대표의 배열 칸에 숫자가 남아 있어도 현재 집합 크기로 읽지 않습니다.

시간 복잡도

경로 압축과 크기 기준 합치기를 함께 쓰면 find와 union은 매우 빠릅니다. 여러 연산의 총비용을 나눈 상각 시간이 O(alpha(n))입니다. 개별 호출의 최악 시간이 상수라는 뜻은 아닙니다.

alpha(n)은 inverse Ackermann function입니다. 이름은 복잡하지만, 알고리즘 문제에서 등장하는 모든 현실적인 n에 대해 거의 5 이하입니다. 그래서 실전에서는 Union-Find 연산을 거의 상수 시간처럼 생각해도 됩니다.

n개 원소 초기화: O(n)
m번 find/union: O(m alpha(n))

단, 이 성능은 두 최적화를 같이 쓸 때의 이야기입니다. 경로 압축이나 크기 기준 합치기를 빼면 특정 입력에서 훨씬 느려질 수 있습니다.

전체 구현

아래는 0-indexed 원소 0부터 n - 1까지를 다루는 기본 구현입니다.

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

#include <algorithm>
#include <vector>
using namespace std;

struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

    bool unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;

        if (size[rootA] < size[rootB]) {
            swap(rootA, rootB);
        }
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        return true;
    }

    int componentSize(int x) {
        return size[find(x)];
    }
};

unite가 bool을 반환하게 만들면 실제로 두 집합이 합쳐졌는지 알 수 있습니다. 사이클 판정이나 컴포넌트 개수 관리에서 유용합니다.

합쳐지지 않은 호출은 세지 않기

처음에는 집합이 n개이고 dsu.unite(a, b)가 true를 반환할 때만 하나 줄어듭니다.

n = 4에서 (0, 1), (1, 2), (0, 2)를 차례로 합치면 마지막 호출은 이미 같은 집합이므로 아무 변화가 없습니다. 결과는 {0, 1, 2}, {3}의 두 집합입니다. 호출 횟수를 빼면 잘못된 답 1이 나옵니다.

대표는 합치는 과정에서 바뀔 수 있습니다. 집합 크기는 예전에 저장한 대표 대신 componentSize(x)로 읽습니다. 기본 Union-Find는 간선을 지워 집합을 다시 나누는 연산을 지원하지 않습니다.

실전 연결: 모임으로 나뉜 팀

모임으로 나뉜 팀은 같은 모임에 나온 사람들을 한 팀으로 묶는 문제입니다. 모임 하나가 {a, b, c, d}라면 모든 쌍을 합칠 필요는 없습니다.

unite(a, b);
unite(a, c);
unite(a, d);

위 세 줄은 병합할 쌍의 순서를 보여 주는 조각입니다. 앞의 구조체를 DSU dsu(n);으로 만들었다면 실제 호출은 dsu.unite(a, b)처럼 객체를 통해 합니다.

첫 사람을 기준으로 나머지를 합치면 모임 안의 사람들은 모두 같은 집합이 됩니다. 모든 모임을 처리한 뒤에는 대표별 componentSize를 한 번씩 모으고, 필요한 순서로 정렬하면 됩니다.

주의할 점은 세 가지입니다.

• 빈 모임이면 기준 원소가 없으므로 아무 것도 하지 않습니다.
• 한 명짜리 모임은 이미 자기 집합에 있으므로 합칠 필요가 없습니다.
• 같은 사람이 모임 안에 여러 번 나와도 unite(x, x)는 false를 반환하고 끝나야 합니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

c++ -std=c++17 -O2 union-find.cpp -o lesson
./lesson < input.txt

다음은 외부 채점기 없이 실행하는 연결 질의 연습입니다. N Q 뒤 Q개 연산을 받으며 1 ≤ N ≤ 200000, 0 ≤ Q ≤ 200000, 원소는 0..N-1입니다.

연산	의미	출력
U a b	두 집합 병합	새로 합쳤으면 1, 이미 같으면 0
Q a b	같은 집합인가	같으면 1, 다르면 0
S a	a가 속한 집합 크기	원소 수
C	현재 집합 수	성공한 병합만 반영한 개수

6 9
U 0 1
U 2 3
U 0 2
S 3
U 1 3
Q 0 3
Q 0 5
C
S 5

출력은 순서대로 다음과 같습니다.

1
1
1
4
0
1
0
3
1

첫 네 연산과 중복 병합은 실험의 기본 예제와 같습니다. 같은 원소 병합은 항상 0, 혼자인 원소의 크기는 1입니다. N=1에서도 그대로 동작합니다. 작은 입력에서 실제 간선을 저장한 뒤 매번 BFS로 연결된 원소를 세어 비교할 수 있습니다.

파일은 원본 DSU와 입력 처리를 포함하며, 범위 밖 원소를 거부합니다. 기본 DSU에 간선 삭제를 추가해서 연결 요소가 자동으로 갈라질 것이라 기대하면 안 됩니다. 삭제가 필요하면 별도 알고리즘을 선택해야 합니다.

기존 Disjoint Set 노트의 과거 코드는 그대로 보존합니다. 그 조각에는 지역 변수 재선언 문제가 있고 크기 기준 병합은 포함되지 않습니다. 이 강의는 경로 압축과 크기 기준 병합을 함께 쓰는 실행 파일을 기준으로 설명합니다.

curl -fsSL 'https://www.readiz.com/records/union-find/index.md'