연결성 질의와 Union-Find
이 구조의 핵심 상태는 “각 원소가 어느 대표자 아래에 있는가”이며 원래 간선 목록 자체가 아닙니다. 그래서 연결 여부를 빠르게 묻는 문제에는 맞지만, 경로 복원·간선 삭제·연결 성분의 이력 조회가 요구되면 추가 구조나 다른 알고리즘이 필요합니다.
무방향 그래프에 간선을 하나씩 추가하면서 두 정점이 이미 연결됐는지 묻는다고 합시다. 매번 전체 그래프를 탐색하는 대신 같은 연결 성분에 속한 원소를 한 집합으로 관리할 수 있습니다. Union-Find 또는 분리 집합 구조는 대표자를 찾는 find와 두 집합을 합치는 union을 제공합니다.
대표자가 같으면 연결돼 있다는 뜻이지만 실제로 어떤 간선을 지나 연결되는지는 알려 주지 않습니다. 부모 배열은 구현상 집합을 표현하는 트리이지 원래 그래프의 경로가 아닙니다.
크기 기반 집합 병합
원소 0~4의 부모는 처음 모두 자기 자신이고 크기는 1입니다. 같은 크기면 첫 인자의 루트를 남기는 정책으로 진행하겠습니다.
| 연산 | 부모 배열 | 루트별 크기 | 성분 수 |
|---|---|---|---|
| 시작 | [0,1,2,3,4] | 모두 1 | 5 |
| union(0,1) | [0,0,2,3,4] | 0:2, 2:1, 3:1, 4:1 | 4 |
| union(2,3) | [0,0,2,2,4] | 0:2, 2:2, 4:1 | 3 |
| union(0,2) | [0,0,0,2,4] | 0:4, 4:1 | 2 |
| find(3), 경로 압축 | [0,0,0,0,4] | 0:4, 4:1 | 2 |
3에서 부모를 따라가면 3→2→0입니다. 경로 압축은 find 도중 지나간 부모를 루트 0으로 바꾸어 다음 탐색을 짧게 합니다. 이때 원래 그래프에 3→0 간선이 생긴 것은 아닙니다.
그림을 글로 읽기
- 원소 3: 압축 전 parent=2
- 원소 2: parent=0
- 루트 0: parent=0 · size=4
- 원소 3 → 원소 2: 기존 부모
- 원소 2 → 루트 0: 기존 부모
- 원소 3 → 루트 0: 압축 뒤 직접 참조
find의 배열 변경과 경로 압축
find(x):
require valid vertex x
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != x:
next = parent[x]
parent[x] = root
x = next
return root
union(a,b):
ra = find(a)
rb = find(b)
if ra == rb: return false
if size[ra] < size[rb]: swap(ra,rb)
parent[rb] = ra
size[ra] += size[rb]
components -= 1
return true
대표자가 같을 때 크기와 성분 수를 다시 변경하면 중복 union으로 값이 틀어집니다. 루트가 아닌 노드의 size는 더 이상 유효한 집합 크기라고 읽지 않습니다. 최소 ID나 합계가 필요하면 살아남은 루트에 메타데이터를 따로 병합합니다. 대표자 자체가 의미 있는 리더라고 가정하지 않습니다.
크기 기반 병합만 쓰면 어떤 노드의 깊이가 하나 늘 때 속한 집합 크기는 적어도 두 배가 됩니다. 따라서 깊이는 O(log n)입니다. 경로 압축까지 조합하면 긴 연산열의 비용은 역 아커만 함수 α(n)을 사용하는 매우 작은 상환 비용으로 제한됩니다. 모든 호출의 최악 시간이 엄밀히 O(1)이라는 뜻은 아닙니다.
rollback과 find의 숨은 변경
union(0,2) 직전에 체크포인트를 저장하고, 병합 후 그 지점으로 되돌리려 한다고 하겠습니다. 병합 뒤 find(3)가 3→2→0 경로를 압축해 parent[3]=0으로 바꾸면, parent[2]와 size[0]만 되돌려서는 충분하지 않습니다. union 전의 parent[3]=2까지 복원해야 하므로, 경로 압축의 변경을 기록하지 않은 rollback은 연결성 상태를 틀리게 남깁니다.
그래서 단순 rollback 변형은 경로 압축 없이 크기 기반 병합만 사용합니다. 성공한 각 union이 바꾼 parent, size, 성분 수를 스택에 쌓아 두고, 체크포인트로 저장한 스택 길이까지 역순으로 되돌립니다.
checkpoint(): return length(history)
unionRollback(a,b):
ra, rb = findWithoutCompression(a), findWithoutCompression(b)
if ra == rb: return false
if size[ra] < size[rb]: swap(ra,rb)
history.push((rb, ra, size[ra]))
parent[rb] = ra
size[ra] += size[rb]
components -= 1
return true
rollback(mark):
require 0 <= mark <= length(history)
while length(history) > mark:
rb, ra, oldSize = history.pop()
parent[rb] = rb
size[ra] = oldSize
components += 1
이 계약은 “최근 union 호출을 한 번 취소”가 아니라 체크포인트까지 복원입니다. 따라서 같은 집합 union은 기록하지 않아도 됩니다. 호출 횟수로 되돌리는 API라면 무변경 호출도 표식으로 기록해야 합니다. 추가 메타데이터가 있다면 모두 복원 대상입니다.
따라서 일반 Union-Find에는 경로 압축을 켜고, 시간 구간 분할이나 분기 탐색처럼 rollback이 필요한 경로에는 압축을 끕니다. 둘을 섞으려면 압축으로 바뀐 모든 부모 포인터를 history에 기록하는 별도 계약이 있어야 하며, “find는 조회이므로 기록할 필요가 없다”는 구현 선택은 성립하지 않습니다.
간선 삭제와 방향 경로의 구분
합친 집합에서 임의 간선을 지웠다고 두 성분으로 나뉜다고 단정할 수 없습니다. 다른 경로가 남을 수 있고 기본 Union-Find는 원래 간선을 보관하지 않습니다. 전체 시간 구간을 미리 아는 오프라인 문제는 각 구간에 union을 적용하고 나올 때 rollback하는 방식으로 처리할 수 있지만, 임의 온라인 삭제를 기본 구조가 즉시 지원하는 것은 아닙니다.
방향 그래프에서 A→B가 있다고 B에서 A로 갈 수 있는 것도 아닙니다. 이 구조의 무방향 연결성과 방향 도달성·강한 연결성을 혼동하지 않습니다. 경로가 필요하면 BFS 등의 탐색에서 부모 간선과 거리를 저장해야 합니다.
집합 분할과 기준 그래프 비교
여러 병합 순서가 다른 대표자를 만들 수 있으므로 부모 배열 하나를 유일한 정답으로 삼지 않습니다. 모든 정점 쌍의 같은 집합 여부를 기준 그래프 탐색과 비교합니다. 자기 union·중복 union·고립 원소·긴 병합열도 넣습니다.
롤백에서는 체크포인트 전후의 연결성·크기·성분 수가 모두 돌아오는지 확인합니다. 경로 압축을 실수로 사용한 변형에 위 3→2→0 사례를 넣으면 간단히 오류를 드러낼 수 있습니다. find가 논리적 조회처럼 보여도 실제 쓰기라는 점 때문에 동시 접근에도 별도 동기화가 필요합니다.
예상 결과는 mark=2를 저장한 뒤 성공한 union 두 개와 find 여러 번을 수행하고 rollback했을 때 부모·루트 size·components가 mark 시점과 바이트 수준으로 같아지는 것입니다. 연결성만 같고 부모 배열이 달라도 논리적으로는 통과할 수 있지만, rollback 구현 검증에서는 압축 여부까지 별도 불변식으로 검사합니다.