Union-Find

Union-Find란?

여러 개의 원소가 있을 때,어떤 원소가 어떤 집합에 속해 있는지 빠르게 알 수 있도록 해주는 자료구조입니다.

• Find: 어떤 원소가 어느 집합에 속해 있는지 찾기
• Union: 두 집합을 하나로 합치기

---

어떤 상황에서 쓰일까?

• 그래프의 사이클 판별
• 크루스칼 알고리즘 (최소 신장 트리)
• 네트워크 연결 여부 판단
• 집합의 묶음 관리

---

기본 구현 (Python)

# 1. 자기 자신을 부모로 초기화
parent = [i for i in range(10)]

# 2. Find 함수 (재귀)
def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x

# 3. Union 함수
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

---

경로 압축 (Path Compression)

Find 연산 시, 루트를 찾을 때 경로를 압축해서 속도 향상

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축!
    return parent[x]

---

Union by Rank (또는 Union by Size)

항상 작은 트리를 큰 트리에 붙여 높이를 최소화
시간복잡도: 거의 O(1)

rank = [0] * 10

def union(x, y):
    root_x = find(x)
    root_y = find(y)

    if root_x == root_y:
        return

    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    else:
        parent[root_y] = root_x
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1

---

사이클 판별 예제

def has_cycle(edges, n):
    parent = [i for i in range(n+1)]
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return True  # 사이클 발생
        parent[root_y] = root_x
        return False

    for a, b in edges:
        if union(a, b):
            return True
    return False

---

항목	설명
자료구조	트리 기반 집합 관리
주요 연산	Find, Union
최적화	Path Compression, Union by Rank
사용 예	싸이클 판별, 크루스칼 알고리즘, 네트워크 그룹핑
시간복잡도	O(α(N)) ≈ O(1) (거의 상수 시간)