서로소 집합 자료구조는 합치기 찾기 자료구조라고 불리기도 한다.
여러 개의 합치기 연산이 주어졌을 때 서로조 집합 자료구조의 동작 과정은 다음과 같다.
※ 과정을 거쳤을 때 의아한 점이 눈에 띄게 된다. Union(1, 4)을 통해서 {1, 4}가 되고 Union(2, 3)을 통해서 {2, 3}이 되고 Union(2, 4)을 통해서 {2, 4}가 되는데 이 때, 큰 번호의 노드를 작은 번호의 노드의 루트노드로 설정하는게 관행이다. 그랬을 때, 3번 노드의 부모 노드는 2번이 되는데 그렇게 된다면 맞지 않게 된다. 이 때, ★재귀★를 사용한다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x): # parent : 부모 테이블, x : 노드의 번호
# 루트 노드를 찾을 때까지 재귀 호출
# 현재 부모가 자기 자신이 아니라면?
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b): # parent : 부모 테이블 a, b : 각각의 노드 번호
a = find_parent(parent, a)
b = find_parent(parent, b)
# 더 큰 번호 값을 갖는 노드의 부모 번호를 작은 번호 값을 갖는 노드의 부모 번호로 교체
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수를 입력 받기
v, e = map(int, input().split())
# 부모 테이블 초기화하기
parent = [0] * (v+1)
# 부모 테이블 상에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# Union(합치기) 연산을 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합을 출력하기
for i in range(1, v+1):
print(find_parent(parent, i))
# 부모 테이블 내용을 출력하기
for i in range(1, v+1):
print(parent[i])