서로소 집합 자료구조는 union과 find 2개의 연산을 활용하므로 union-find 자료구조라고 불리기도 한다.
union 연산은 2개의 집합을 하나의 집합으로 합치는 연산이다.
find 연산은 특정 원소가 속한 집단이 어떤 집합인지 알려주는 연산이다.
서로소 집합 자료구조는 원소들 사이의 관계를 나타내기 위해 parent 리스트를 선언하여 이용하는데,
초기 parent 값은 자기 자신으로 설정한다. parent = [x for x in range(v+1)]
기본적으로 두 노드를 하나의 집합으로 합칠 때는 큰 노드가 작은 노드를 가리키도록 한다. (값이 더 작은 원소를 가지는 노드가 루트 노드가 되도록 함)
union(a, b):
# a의 루트 노드를 x, b의 루트 노드를 y라고 가정(x는 a이며, y는 b인 경우도 가능함)
a와 b의 루트 노드인 x와 y를 각각 찾는다.(find_parent)
x와 y 중 크기가 큰 노드의 부모를 크기가 작은 노드로 설정한다.
union 연산 예시
union(1, 4) -> union(2, 3) -> union(2, 4) -> union(5, 6)
# 서로소 집합 알고리즘
import sys
'''
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent,parent[x])
else:
return x
'''
# 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있다.
# 경로 압축은 find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법이다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
# x의 부모 값을 부모의 부모를 찾아서 갱신하는 과정을 재귀적으로 반복
return parent[x]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a > b: parent[a] = b
else: parent[b] = a
v, e = map(int, sys.stdin.readline().split())
parent = [i for i in range(v+1)]
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
union(parent, a, b)
for i in range(1, n+1): print(find_parent(parent, i), end=" ")
print()
for i in range(1, n+1): print(parent[i], end=" ")
서로소 집합을 활용한 무방향 그래프에서의 사이클 판별
서로소 집합은 무방향 그래프 내에서의 사이클만을 판별할 수 있다.
방향 그래프에서의 사이클 여부는 DFS를 이용해서 판별할 수 있다.
노드 a와 노드 b를 union할 때,
a의 루트와 b의 루트를 확인하는 과정에서 두 노드의 루트가 같다면 사이클이 존재하는 것임.
# 서로소 집합을 활용한 사이클 판별
import sys
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a > b: parent[a] = b
else: parent[b] = a
cycle = False # 사이클 발생 여부
v, e = map(int, sys.stdin.readline().split())
parent = [x for x in range(v+1)]
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
if find_parent(parent, a) == find_parent(parent, b):
cycle = True; break
else: union(parent, a, b)
if cycle: print("Cycle : True")
else: print("Cycle : False")