#유니온 파인드

Union-Find(서로소 집합)는 겹치지 않는 집합들을 부모 포인터 트리로 관리한다. 각 원소는 부모를 따라가며 대표(root)를 찾고, 같은 대표를 가진 두 원소는 같은 집합에 속한다.

• 초기화: 각 원소를 자기 자신의 부모로 둔다.
• find(x): 부모를 따라 집합의 대표를 찾는다.
• union(a, b): 두 대표가 다르면 한 집합을 다른 집합에 합친다.

find를 수행한 경로의 부모를 대표로 바로 바꾸면 다음 탐색이 짧아진다. union 때는 작은 트리를 큰 트리 아래에 붙이면 트리가 한쪽으로 길어지는 것을 막는다.

root_a = find(a)
root_b = find(b)
if root_a != root_b:
    if size[root_a] < size[root_b]:
        root_a, root_b = root_b, root_a
    parent[root_b] = root_a
    size[root_a] += size[root_b]

경로 압축과 크기 또는 rank 기준 합치기를 함께 사용하면 연산의 분할 상환 시간은 사실상 상수에 가까운 `O(α(n))`이다.

두 정점의 연결 여부를 반복해서 묻거나, 간선을 추가하며 연결 요소를 합치는 문제에 적합하다. 최소 신장 트리의 크루스칼 알고리즘처럼 그래프 외의 묶음 관계도 관리할 수 있다.

집합마다 크기, 합계, 가장 오른쪽 인덱스 같은 정보를 root에 저장할 수도 있다. 합칠 때는 두 root의 정보를 함께 갱신해야 한다. 호텔 방 배정처럼 번호가 이어진 점유 구간에서는 root에 구간의 오른쪽 끝을 저장해 다음 빈 번호를 찾는다.

• 대표를 찾지 않고 원소의 현재 부모만 비교해 같은 집합인지 판정하는 경우
• 이미 같은 집합인 두 root를 다시 합쳐 사이클 또는 잘못된 크기를 만드는 경우
• 크기·최댓값 등 root에 저장한 부가 정보를 합칠 때 갱신하지 않는 경우
• 원소 범위가 매우 큰데 전체 범위 크기의 배열을 만들어 메모리를 낭비하는 경우