Trees: Union-Find (Disjoint Set Union, DSU)

✅ Union-Find (Disjoint Set Union, DSU)란?

📌 무엇인가요?

• 여러 개의 서로소 집합(disjoint sets) 을 관리하는 자료구조입니다.
• 주로 그래프에서 사이클을 판별하거나, 네트워크 연결 여부, 클러스터 관리 등에 사용됩니다.

---

✅ 주요 연산 두 가지

연산	설명
find(x)	원소 x가 속한 집합의 대표(루트 노드) 를 찾음
union(x, y)	x와 y가 속한 두 집합을 하나로 합침

---

✅ 최적화 기법

1. Path Compression (경로 압축)
   find(x) 호출 시, 경로에 있는 노드들을 직접 루트에 연결해서 다음 검색을 빠르게 함
2. Union by Rank / Height
   집합을 합칠 때, 작은 트리를 큰 트리에 붙임 → 트리 깊이를 줄여 성능 개선

---

✅ 시간복잡도

• 거의 O(1) 에 가깝습니다 (아커만 함수 역함수 기반)
• 매우 많은 union/find 연산을 해도 빠르게 동작합니다

---

✅ 코드 설명 (줄별 상세 주석 포함)

class UnionFind:
    def __init__(self, n):
        self.par = {}     # 각 노드의 부모를 저장하는 딕셔너리
        self.rank = {}    # 각 루트 노드의 랭크(트리 깊이 또는 크기 추정치)를 저장

        for i in range(1, n + 1):  # 노드 번호가 1부터 n까지일 때
            self.par[i] = i        # 처음에는 자기 자신이 부모 (각 노드가 독립 집합)
            self.rank[i] = 0       # 처음엔 모두 rank 0 (깊이 0의 트리)
	
    """
    # Find 연산: n이 속한 집합의 루트(대표)를 반환
    """
    # Path compression 적용
    def find(self, n):
        p = self.par[n]  # 현재 노드의 부모
        while p != self.par[p]:  # 부모가 자기 자신이 아니면 (루트가 아니면)
            self.par[p] = self.par[self.par[p]]  # 중간 부모를 루트로 올려서 경로 압축
            p = self.par[p]  # 위로 계속 올라가기
        return p  # 루트 노드를 반환
	
    """
    # Union 연산: 두 집합을 하나로 합침 - 작은 트리 -> 큰 트리에 merge    
    """
    # Union by rank 적용
    # 이미 같은 집합이면 False, 새로 합쳐졌다면 True 반환
    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)  # 각각의 루트를 찾음
        if p1 == p2:
            return False  # 이미 같은 집합에 속해 있음 → 아무 것도 하지 않음

        # rank가 높은 쪽을 부모로 만듦 (작은 트리를 큰 트리에 붙임)
        if self.rank[p1] > self.rank[p2]:
            self.par[p2] = p1  # p2를 p1에 붙임
        elif self.rank[p1] < self.rank[p2]:
            self.par[p1] = p2  # p1을 p2에 붙임
        else:
            # rank가 같다면 아무 쪽이나 붙이고, rank를 1 올림
            self.par[p1] = p2
            self.rank[p2] += 1
        return True  # 새로운 union이 발생했음을 의미

 

rank 가 높으면, 더 부모라는 것임!!

 

class UnionFind:
    def __init__(self, n: int):
        # parent[i] = i는 처음엔 모든 노드가 자기 자신이 루트임
        self.parent = [i for i in range(n)]  # 각 노드의 부모 (초기에는 자기 자신)
        self.size = [1] * n                  # 각 루트 노드가 포함한 컴포넌트 크기 (초기 1)
        self.num_components = n              # 연결된 컴포넌트 수 (처음엔 n개)

    def find(self, x: int) -> int:
        # 루트 노드를 찾는 함수 (Path Compression 적용)
        if x != self.parent[x]:  # x가 루트가 아니면
            self.parent[x] = self.find(self.parent[x])  # 재귀적으로 루트 찾고 경로 압축
        return self.parent[x]  # 루트 반환

    def isSameComponent(self, x: int, y: int) -> bool:
        # x와 y가 같은 집합(컴포넌트)에 속하는지 확인
        return self.find(x) == self.find(y)

    def union(self, x: int, y: int) -> bool:
        # x와 y가 속한 집합을 하나로 합침 (size 기준으로 작은 쪽을 큰 쪽에 붙임)
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            # 더 작은 size를 더 큰 size 쪽에 붙임 (Union by Size)
            if self.size[root_x] < self.size[root_y]:
                self.parent[root_x] = root_y  # 작은 쪽(root_x)을 큰 쪽(root_y)에 붙임
                self.size[root_y] += self.size[root_x]
            else:
                self.parent[root_y] = root_x
                self.size[root_x] += self.size[root_y]

            self.num_components -= 1  # 연결된 컴포넌트 수 감소
            return True  # 새로운 연결이 생겼음을 의미

        return False  # 이미 같은 컴포넌트임

    def getNumComponents(self) -> int:
        # 현재 연결된 컴포넌트 개수 반환
        return self.num_components

 

✅ 핵심 개념 비교

속성	설명
parent[i]	노드 i의 부모 노드를 저장 (자기 자신일 경우 루트)
size[i]	루트 i가 대표하는 컴포넌트의 크기
num_components	현재 몇 개의 독립적인 집합이 있는지 추적

---

✅ 특징 요약

기능	설명
find(x)	경로 압축으로 루트 빠르게 찾기
union(x, y)	사이즈 비교하여 더 작은 트리를 큰 트리에 붙이기
isSameComponent(x, y)	x와 y가 같은 집합에 속해 있는지 확인
getNumComponents()	현재 남아있는 독립 집합(컴포넌트) 개수

✅ 사용 예시

uf = UnionFind(5)           # 0 ~ 4번 노드 생성
uf.union(0, 1)              # 0과 1 연결
uf.union(1, 2)              # 1과 2 연결 (0-1-2 연결됨)
print(uf.isSameComponent(0, 2))  # True
print(uf.getNumComponents())     # 3 (두 번 union 했으니 5 → 3)