분리 집합 (Disjoint Set, Union-Find)

정의

분리 집합 (Disjoint Set, Union-Find) 은 서로 겹치지 않는 집합들을 관리하며, 다음 두 연산을 거의 상수 시간 (amortized O(α(N)), α는 역 아커만 함수) 에 처리하는 자료구조.

• find(x): x 가 속한 집합의 대표 원소 (root) 반환.
• union(x, y): x 와 y 가 속한 집합을 합침.

추가 연산: same(x, y) = find(x) == find(y) (같은 집합인지 판별).

문제 상황과 동기

동적 연결성 (dynamic connectivity): 노드 간 연결 관계를 추가하면서, “두 노드가 같은 컴포넌트에 있는가?” 를 빠르게 묻는다.

• naive: 각 컴포넌트마다 리스트. union 은 O(N) 병합, find 는 O(N) 순회.
• Union-Find (최적화 없음): 트리 구조. 최악 O(N) (skewed tree).
• path compression + union by rank: amortized O(α(N)) ≈ O(1).

α(N) 은 역 아커만 함수. N ≤ 10^80 일 때도 α(N) ≤ 4. 실질적 상수.

시각화

핵심 아이디어

기본 구조

각 원소는 parent[x] 포인터를 가짐. parent[x] == x 이면 x 가 root (대표 원소).

초기화:
    parent[i] = i  (모두 독립 집합)

find(x):
    while parent[x] != x:
        x = parent[x]
    return x

union(x, y):
    rx = find(x)
    ry = find(y)
    if rx != ry:
        parent[rx] = ry  (또는 ry 를 rx 로)

Path Compression (경로 압축)

find(x) 과정에서 거쳐간 모든 노드를 직접 root 에 연결. 다음 find 가 O(1) 에 가까워짐.

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 재귀 + 압축
    return parent[x];
}

또는 반복 + 2-pass:

int find(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root];
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

Union by Rank (랭크 기준 합침)

트리 높이 (또는 크기) 를 rank[x] 로 관리. 작은 트리를 큰 트리 아래 붙여 높이 증가 최소화.

int rank[N];  // 초기 0

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) swap(x, y);
    parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
}

또는 union by size (집합 크기 추적):

int size[N];  // 초기 1

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    parent[y] = x;
    size[x] += size[y];
}

복잡도 분석

• path compression 만: amortized O(log N).
• union by rank 만: 최악 O(log N).
• 둘 다 적용: amortized O(α(N)) ≈ O(1).

α(N) 은 매우 느리게 증가. N = 2^65536 일 때도 α(N) = 5.

구현

기본 (path compression + union by rank)

// Union-Find, path compression + union by rank
#include <bits/stdc++.h>
using namespace std;
int parent[100001], rnk[100001];
int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
void unite(int x, int y) {
  x = find(x); y = find(y);
  if (x == y) return;
  if (rnk[x] < rnk[y]) swap(x, y);
  parent[y] = x;
  if (rnk[x] == rnk[y]) rnk[x]++;
}
bool same(int x, int y) { return find(x) == find(y); }
int main() {
  int N, M; cin >> N >> M;
  for (int i = 1; i <= N; i++) parent[i] = i, rnk[i] = 0;
  while (M--) {
      int op, a, b; cin >> op >> a >> b;
      if (op == 0) unite(a, b);
      else cout << (same(a, b) ? "YES" : "NO") << "\n";
  }
}

# Union-Find, path compression + union by rank
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
​
parent = []
rnk = []
​
def find(x):
  if parent[x] != x:
      parent[x] = find(parent[x])
  return parent[x]
​
def unite(x, y):
  x, y = find(x), find(y)
  if x == y: return
  if rnk[x] < rnk[y]: x, y = y, x
  parent[y] = x
  if rnk[x] == rnk[y]: rnk[x] += 1
​
def same(x, y):
  return find(x) == find(y)
​
N, M = map(int, input().split())
parent = list(range(N + 1))
rnk = [0] * (N + 1)
out = []
for _ in range(M):
  op, a, b = map(int, input().split())
  if op == 0:
      unite(a, b)
  else:
      out.append("YES" if same(a, b) else "NO")
print("\n".join(out))

// Union-Find, path compression + union by rank
import java.util.*;
import java.io.*;
public class Main {
  static int[] parent, rnk;
  static int find(int x) {
      if (parent[x] != x) parent[x] = find(parent[x]);
      return parent[x];
  }
  static void unite(int x, int y) {
      x = find(x); y = find(y);
      if (x == y) return;
      if (rnk[x] < rnk[y]) { int t = x; x = y; y = t; }
      parent[y] = x;
      if (rnk[x] == rnk[y]) rnk[x]++;
  }
  static boolean same(int x, int y) { return find(x) == find(y); }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      parent = new int[N + 1];
      rnk = new int[N + 1];
      for (int i = 1; i <= N; i++) parent[i] = i;
      StringBuilder sb = new StringBuilder();
      while (M-- > 0) {
          st = new StringTokenizer(br.readLine());
          int op = Integer.parseInt(st.nextToken());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          if (op == 0) unite(a, b);
          else sb.append(same(a, b) ? "YES" : "NO").append('\n');
      }
      System.out.print(sb);
  }
}

5 7
0 1 2
0 2 3
1 1 3
1 1 4
0 3 4
1 1 4
1 2 5

YES
NO
YES
NO

union by size (집합 크기 추적)

// Union-Find, union by size
#include <bits/stdc++.h>
using namespace std;
int parent[100001], siz[100001];
int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
void unite(int x, int y) {
  x = find(x); y = find(y);
  if (x == y) return;
  if (siz[x] < siz[y]) swap(x, y);
  parent[y] = x;
  siz[x] += siz[y];
}
int get_size(int x) { return siz[find(x)]; }
int main() {
  int N, M; cin >> N >> M;
  for (int i = 1; i <= N; i++) parent[i] = i, siz[i] = 1;
  while (M--) {
      int op, a, b; cin >> op >> a >> b;
      if (op == 0) unite(a, b);
      else if (op == 1) cout << (find(a) == find(b) ? "YES" : "NO") << "\n";
      else cout << get_size(a) << "\n";  // op == 2
  }
}

5 6
0 1 2
2 1 0
0 2 3
2 1 0
0 4 5
2 4 0

2
3
2

복잡도

공간: O(N).

변형 / 활용

연결 컴포넌트 개수

초기 N 개. union 성공할 때마다 -1.

int components = N;
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    parent[y] = x;
    components--;
}

각 집합의 원소 리스트

vector<int> members[root] 로 관리. union 시 병합. O(N log N) 총.

Undo (rollback)

union 이력을 stack 에 저장, 역순 복구. persistent DSU 는 path copying.

부분적 순서 (partial order)

x < y 관계 추가. find 시 거리 누적. weighted Union-Find.

오프라인 동적 연결성

간선 추가 / 삭제 쿼리를 정렬, segment tree + Union-Find.

함정

1. parent[x] 초기화 누락

parent[i] = i 안 하면 쓰레기값. 세그폴트 또는 무한 루프.

2. find 없이 parent 직접 비교

if (parent[x] == parent[y]) 는 틀림. 반드시 find(x) == find(y).

3. 재귀 stack overflow (Python)

sys.setrecursionlimit(200000) 필수. 또는 반복 구현.

4. rank vs size 혼용

둘 다 작동하지만 혼용하면 의도와 다름. 일관성 유지.

5. union 후 size/rank 업데이트 누락

union by size 에서 size[x] += size[y] 빼먹으면 틀림.

BOJ 연습 문제

참고

• 최소 신장 트리
• 크루스칼 알고리즘
• 동적 연결성