---
id: "lessons/union-find"
title: "Union-Find: 연결하고 대표를 찾기"
description: "집합을 합치고 경로를 압축하며, 중복 병합과 집합 크기를 다룹니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","자료구조"]
url: "https://www.readiz.com/records/union-find/"
markdownUrl: "https://www.readiz.com/records/union-find/index.md"
---

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

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

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

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

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

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

[원문 그림: Union-Find의 핵심 연산 크게 보기](https://www.readiz.com/assets/lessons/connectivity/union-find-dsu-operations.svg)

## 집합을 숲으로 표현하기

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

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

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

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

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

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

## find: 대표 찾기

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

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

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

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

## 경로 압축

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

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

[원문 그림: 경로 압축 전후 크게 보기](https://www.readiz.com/assets/lessons/connectivity/union-find-path-compression.svg)

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

## union: 대표끼리 합치기

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

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

## 크기 기준 합치기

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

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

[원문 그림: 크기 기준 합치기 크게 보기](https://www.readiz.com/assets/lessons/connectivity/union-find-union-by-size.svg)

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

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

![0과 1, 2와 3을 각각 합친 뒤 대표 2를 0 밑에 붙이면 3은 2를 거쳐 0으로 갑니다. find(3)은 부모를 0으로 줄이고, 같은 집합인 1과 3을 다시 합쳐도 집합 수는 줄지 않습니다.](https://www.readiz.com/assets/lessons/connectivity/dsu-trace.svg)

[그림 크게 보기](https://www.readiz.com/assets/lessons/connectivity/dsu-trace.svg) · [부모 배열과 집합을 움직이는 실험](https://www.readiz.com/learn/explore/?demo=dsu)

원소가 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 연산을 거의 상수 시간처럼 생각해도 됩니다.

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

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

## 전체 구현

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

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
#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는 간선을 지워 집합을 다시 나누는 연산을 지원하지 않습니다.

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

[모임으로 나뉜 팀](https://h.readiz.com/practice/TEAMSIZE)은 같은 모임에 나온 사람들을 한 팀으로 묶는 문제입니다. 모임 하나가 `{a, b, c, d}`라면 모든 쌍을 합칠 필요는 없습니다.

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

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

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

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

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

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

[C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/connectivity/union-find.cpp)

```sh
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`     | 현재 집합 수     | 성공한 병합만 반영한 개수      |

```text
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
```

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

```text
1
1
1
4
0
1
0
3
1
```

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

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

[기존 Disjoint Set 노트](https://www.readiz.com/notes/data-structure/tree/disjointset/)의 과거 코드는 그대로 보존합니다. 그 조각에는 지역 변수 재선언 문제가 있고 크기 기준 병합은 포함되지 않습니다. 이 강의는 경로 압축과 크기 기준 병합을 함께 쓰는 실행 파일을 기준으로 설명합니다.

## 관련 문서

- [Disjoint Set](https://www.readiz.com/notes/data-structure/tree/disjointset/index.md)