서로소 집합과 사이클 판별

서로소 집합

서로소 집합이란, 공통 원소가 없는 두 집합을 의미한다. 예를 들어, 집합 A와 집합 B가 있을 때, A와 B가 서로소 집합이라면 A와 B는 공통 원소를 갖지 않는다.

서로소 집합 자료구조는 원소들을 서로소 부분 집합들로 나누어 관리하는 자료구조이다. 이 자료구조는 'union-find' 자료구조라고도 불리며, 주요 연산으로는 'union'과 'find'가 있다. 두 집합이 서로소 관계인지 확인할 수 있다는 말은, 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말과 같다.

union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
1. A와 B의 루트 노드 A’, B’를 찾는다.
2. A’를 B’의 부모 노드로 설정한다. (B’가 A’를 가리키도록 한다)
모든 union(합집합) 연산을 처리할 때까지 위 과정을 반복한다.

경로 압축 방법 (부모 노드를 찾을 때 부모 테이블을 갱신)을 사용한 서로소 집합 알고리즘의 시간 복잡도는 $O(V + M( 1 + log_{2-M/V}))$ 이다.

서로소 집합 예시 코드

# 재귀적으로 부모 노드를 탐색 (FIND)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 노드 a, b의 합집합 연산 수행 (UNION)
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# n = 노드의 수, m = 연산 횟수
n, m = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (n+1)
# 노드의 부모를 자기 자신으로 설정
for x in range(n+1):
    parent[x] = x

for _ in range(m):
    i, a, b = map(int, input().split())
		# a와 b의 합집합 연산 수행
    if i == 0:
        union_parent(parent, a, b)
    # a와 b의 부모가 같은지 조회
    else:
        pa = find_parent(parent, a)
        pb = find_parent(parent, b)
        print('YES' if pa == pb else 'NO')

서로소 집합과 사이클 판별

SERIES: 알고리즘 (9)

서로소 집합

서로소 집합 예시 코드

추천 문제