유니온 파인드

어떤 문제를 푸는가

원소들이 여러 그룹으로 나뉘어 있고, 다음 두 연산을 빠르게 처리해야 합니다.

• Union(a, b) — a가 속한 그룹과 b가 속한 그룹을 합친다.
• Find(a) — a가 속한 그룹의 대표를 알려준다 (같은 그룹인지 비교용).

"두 도시가 연결되어 있는가?", "사이클이 생기는가?" 같은 동적 연결성 질문을
거의 상수 시간에 답하는 자료구조가 유니온 파인드(분리 집합, DSU)입니다.

기본 구조: 부모 포인터 숲

각 원소는 부모를 가리키는 parent 배열로 표현합니다. 루트는 자기 자신을
가리키며, 그 루트가 그룹의 대표입니다.

parent: 1→1   2→1   3→1   4→4   5→4
그룹: {1,2,3}, {4,5}

Find는 부모를 따라 루트까지 올라가고, Union은 한 루트를 다른 루트 밑에
붙입니다. 그냥 두면 트리가 한 줄로 길어져 Find가 \(O(N)\)이 될 수 있습니다.
두 가지 최적화로 이를 거의 상수로 만듭니다.

최적화 1 — 경로 압축 (Path Compression)

Find 도중 지나친 모든 정점을 루트에 직접 매답니다. 다음에 같은 정점을
찾을 땐 한 번에 루트에 도달합니다.

find(3): 3→1 ... 이후 3은 곧장 1을 가리킨다

최적화 2 — 합치기 기준 (Union by Rank / Size)

Union 시 작은 트리를 큰 트리 밑에 붙입니다. 그래야 높이가 천천히
자랍니다. 트리의 높이(rank)나 크기(size) 둘 중 하나를 기준으로 씁니다.

복잡도

두 최적화를 함께 쓰면 \(m\)번의 연산이

$$ O(m \cdot \alpha(N)) $$

에 처리됩니다. 여기서 \(\alpha\)는 역 아커만 함수 로, 현실의 모든 입력에서
\(\alpha(N) \le 4\) 입니다. 즉 사실상 연산당 상수 시간입니다. 경로 압축만, 혹은
랭크만 써도 \(O(\log N)\)은 보장되지만, 둘 다 쓰는 것이 표준입니다.

무엇을 표현할 수 있나

마지막 성질이 크루스칼 MST에서 핵심으로 쓰입니다. 다음 강의에서 구현과
대표 응용을 다룹니다.

표준 구현 (C++)

경로 압축 + union by size를 함께 쓴 형태입니다.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> par, sz;
    DSU(int n) : par(n), sz(n, 1) {
        iota(par.begin(), par.end(), 0);   // par[i] = i
    }
    int find(int x) {
        while (par[x] != x) {
            par[x] = par[par[x]];          // 경로 절반 압축
            x = par[x];
        }
        return x;
    }
    bool unite(int a, int b) {             // 합쳤으면 true
        a = find(a); b = find(b);
        if (a == b) return false;          // 이미 같은 그룹 → 사이클
        if (sz[a] < sz[b]) swap(a, b);     // 큰 쪽을 부모로
        par[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

find를 반복문으로 짠 "경로 절반 압축(path halving)"은 재귀 없이도 동일한
점근 복잡도를 주며 스택 오버플로 걱정이 없습니다.

재귀형 find (자주 보는 형태)

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

깔끔하지만 정점이 매우 많고 입력이 일렬이면 재귀 깊이가 깊어질 수 있습니다.

파이썬 구현

import sys
sys.setrecursionlimit(1 << 20)

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]   # 경로 절반 압축
            x = self.par[x]
        return x

    def unite(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.par[b] = a
        self.sz[a] += self.sz[b]
        return True

흔한 함정

• 초기화 누락 — 모든 par[i] = i로 시작해야 합니다. iota를 잊으면 0번
  루트로 다 묶입니다.
• rank/size를 안 갱신 — union 시 기준값을 갱신하지 않으면 최적화가 무력화됩니다.
• 압축을 한 번만 — find가 항상 루트를 반환하고 그 과정에서 압축까지
  하도록 해야 합니다.

대표 응용

• 크루스칼 MST — 간선을 가중치 순으로 보며 unite가 사이클을 만들지
  않을 때만 채택. 이것이 4강 최소 신장 트리의 토대입니다.
• 연결 요소 세기 — 모든 간선을 합친 뒤 루트 개수.
• 오프라인 "연결되었는가" 질의 — 간선 추가 + 연결 판정을 섞어 처리.
• 가중 유니온 파인드 — 루트까지의 상대값(예: 차이, 패리티)을 함께 저장하면
  "a와 b의 차이는 d" 같은 제약을 관리할 수 있습니다.

DSU는 간선을 지우는 연산은 직접 지원하지 못한다는 점을 기억하세요. 삭제가
필요하면 롤백 DSU(오프라인 동적 연결성)로 확장합니다.

출제 신호

유니온 파인드(분리 집합)는 다음 신호에서 거의 자동으로 선택됩니다.

• "두 원소가 같은 그룹인가?"를 묻는 질의가 합치기 연산과 섞여 들어옴
• "네트워크를 연결한다", "친구의 친구는 친구", "같은 팀으로 합친다"
• 연산이 온라인(질의가 순서대로 와서 즉시 답해야 함)이고 분리(split)는 없음
• 간선이 시간순으로 추가되며 "언제 처음 연결되는가"를 묻는 문제
• 크루스칼 MST의 내부 부품으로 (사이클 판정)

연산 횟수 \(N, Q \le 10^5{\sim}10^6\)이어도 두 최적화를 켜면 사실상 상수
시간(\(O(\alpha(N))\))이라 규모 걱정은 없습니다. 단, 분리/삭제가 필요하면
유니온 파인드 단독으로는 안 됩니다(오프라인 처리나 다른 구조 필요).

풀이 결정 절차

1. 필요한 연산이 union과 find(같은 집합 판정)뿐인지 확인합니다.
2. 집합에 대해 추가로 유지할 값이 있는지 봅니다 — 집합 크기, 원소 합 등은
   루트에만 저장하고 union 때 병합하면 됩니다.
3. "관계의 종류"가 둘 이상(적/아군, 같다/다르다)이면 정점을 2배로 늘리는
   확장 유니온 파인드 또는 가중치 유니온 파인드를 고려합니다.
4. 복잡도는 거의 항상 통과하므로, 오히려 재귀 깊이(파이썬)와 초기화
   누락이 실패 원인입니다.

자주 하는 실수

첫째, 경로 압축 누락. 압축 없는 find는 최악에 체인이 길이 \(N\)짜리
연결 리스트가 되어 질의당 \(O(N)\), 전체 \(O(NQ)\)로 시간 초과가 납니다.

// 압축 없음 — 최악 O(N) 체인
int find(int x) { return parent[x] == x ? x : find(parent[x]); }

// 경로 압축 — 재귀 결과를 부모에 기록
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

둘째, union을 루트가 아닌 원소끼리 연결하는 실수입니다.

void unite(int a, int b) {
    a = find(a); b = find(b);      // 반드시 루트로 올린 뒤
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b); // 크기 기준 합치기 (rank 도 가능)
    parent[b] = a;
    sz[a] += sz[b];
}

parent[b] = a를 루트가 아닌 원본 인덱스로 하면 집합 정보가 조용히 깨지고,
작은 테스트에선 통과하다가 큰 입력에서만 틀리는 골치 아픈 버그가 됩니다.

셋째, 파이썬의 재귀 한도 — \(N \ge 10^5\)면 재귀 find가 RecursionError를
냅니다. 반복문 버전으로 바꾸거나 sys.setrecursionlimit을 올리세요.

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:        # 두 번째 패스로 경로 압축
        parent[x], x = root, parent[x]
    return root

마지막으로 parent[i] = i 초기화 누락, 그리고 테스트케이스가 여러 개일 때
배열을 재초기화하지 않는 실수도 단골입니다.

연습 방법

사이드바 연습 목록의 순수 "집합 판정" 문제로 압축+크기 합치기 템플릿을
암기 수준으로 만들고, 그다음 집합 크기/합을 루트에 들고 다니는 문제,
마지막으로 적·아군 같은 관계 확장 문제로 올라가세요. 템플릿을 칠 때마다
"루트로 올렸는가, 압축했는가, 초기화했는가" 세 가지를 점검하는 습관이
핵심입니다. 태그된 문제 3문제 이상 해결 시 이 알고리즘이 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.