Union-Find (합집합 찾기) 알고리즘

그래프 관계에서 합집합을 찾을 때 유용

parent = [i for i in range(5)]  # 부모테이블 초기화 (자기 자신을 부모로 갖도록)

# 재귀적으로 파고들어 같은 것을 가리키도록 설정함
def find(x):
    # parent는 0부터 시작함(parent[0]은 0임)
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

# x와 y가 같은 값을 가리키도록 하여 집합을 묶음
def union(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        # 더 작은 원소를 부모로 삼도록 설정(=오른쪽 원소의 부모값을 왼쪽 원소로 설정)
        parent[y] = x

union(1, 4)
# print(parent)
# [0, 1, 2, 3, 1]

union(2, 4)
# print(parent)
# [0, 2, 2, 3, 1]

result = []

for i in range(1, len(parent)):
    result.append(find(i))

print(set(result))