유니온 파인드(Disjoint-set)

💡서로소 집합

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들
• 즉 교집합이 없다
• 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분한다. 이를 대표자라 함

상호배타집합을 표현하는 방법

• 연결리스트
• 트리

상호배타집합 연산

• Make-Set(x)
• Find-Set(x)
• Union(x, y) - 대표원소를 합쳐라

Make-Set(x): 유일한 멤버 x를 포함하는 새로우 ㄴ집합을 생성하는 연산

def Make_Set(x):
       p[x] = x # 나 자신을 가리킴

Find_Set(x): x를 포함하는 집합을 찾는 연산

def Find_Set(x)
    if x == p[x]: return x
    else:
        return Find_Set(p[x])

# 반복구조
def Find_set(x):
    while x != p[x]:
        x = p[x]
    return x

Union(x, y): x와 y를 포함하는 두 집합을 통합하는 연산

def Union(x, y):
    p[Find_Set(y)] = Find_Set(x)

연산의 효율을 높이는 방법

• Rank를 이용한 Union
  • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크라는 이름으로 저장한다
  • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다
• Path compression
  • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾸어 준다.

백준 1717 집합의 표현

https://www.acmicpc.net/problem/1717

1. {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합
2. 명령어가 0이면 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다
3. 명령어가 1이면 a와 b가 같은 집합에 포함되어 있는지를 확인

코드

# BOJ 1717 집합의 표현 - 유니온파인드 골드 4 김수만
# x를 포함하는 집합 찾기
def find_set(x):
    while x != P[x]:
        x = P[x]
    return x
# x와 y 포함하는 두 집합 통합
def union(x, y):
    root_x, root_y = find_set(x), find_set(y)
    P[max(root_x, root_y)] = min(root_y, root_x)

N, M = map(int, input().split())
P = [0] * (N + 1)
# 처음엔 자기 자신 가리키게
for i in range(N + 1):
    P[i] = i
for i in range(M):
    cal, a, b = map(int, input().split())
    # a와 b가 같은 경우는 연산 패스해야 시간초과 안남
    if cal == 0:
        if a != b:
            union(a, b)
    else:
        if a == b:
            print("YES")
        elif find_set(a) == find_set(b):
            print("YES")
        else:
            print("NO")