(1) naive한 구현
# (1) naive한 구현
def find_parent(parent, x):
if parent[x] != x:
return find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa > pb: parent[pa] = pb
else: parent[pb] = pa
import sys
n, m = map(int, sys.stdin.readline().split())
parent = [x for x in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
union(parent, a, b)
for i in range(1,n+1): print(i, ":", find_parent(parent, i))
이렇게 구현하는 경우 다음 그림과 같은 경우 매우 비효율적으로 동작하게 된다.
(2) 경로 압축(Path Compression)
경로 압축 기법을 활용하면 find_parent 호출 시 최상위 부모 노드로 거슬러 올라가면서 거처가는 노드들의 부모를 최상위 노드로 업데이트해 주기 때문에 위의 그림과 같은 경우에도 효율적으로 작동하는 분리 집합으로 만들어 줄 수 있다.
find_parent(parent, 7) 호출 시 7에서 1(최상위 노드)에 이르는 경로에 있는 모든 노드의 parent를 1로 만들어 주게 된다!!
# (2) 경로 압축 (Path Compression)
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa > pb: parent[pa] = pb
else: parent[pb] = pa
import sys
n, m = map(int, sys.stdin.readline().split())
parent = [x for x in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
union(parent, a, b)
for i in range(1,n+1): print(i, ":", find_parent(parent, i))
(3) Union by Size
parent를 기록하는 리스트와 더불어 size를 기록하는 리스트를 선언하여 관리한다.
노드 a와 노드 b를 union해야 할 경우, a의 최상위 노드(pa)의 size와 b의 최상위 노드(pb)의 size를 비교하여 size가 큰 노드가 size가 더 작은 노드의 부모가 되도록 만든 후, 부모가 된 노드의 size에 자식이 된 노드의 size를 더해 준다.
두 분리 집합을 union할 경우, 자식이 되는 쪽의 parent 값들을 갱신해 주어야 하고 이 과정에서 시간이 소요되므로 두 집합의 size를 비교하여 더 작은 쪽이 자식이 되도록 만들어 주면 소요되는 시간을 줄일 수 있다.
# (3) Union by size
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa != pb:
if size[pa] > size[pb]:
parent[pb] = pa; size[pa] += size[pb]
else:
parent[pa] = pb; size[pb] += size[pa]
import sys
n, m = map(int, sys.stdin.readline().split())
parent = [x for x in range(n+1)]
size = [1 for x in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
union(parent, a, b)
for i in range(1,n+1): print(i, ":", find_parent(parent, i))(4) Union by Rank
parent를 기록하는 리스트와 더불어 rank(하위 노드의 깊이)를 기록하는 리스트를 선언하여 관리한다.
노드 a와 노드 b를 union해야 할 경우, a의 최상위 노드(pa)의 rank와 b의 최상위 노드(pb)의 rank를 비교하여 rank가 큰 노드가 rank가 더 작은 노드의 부모가 되도록 만든 후
부모가 된 노드의 rank와 자식이 된 노드의 rank가 동일한 경우, 부모가 된 노드의 rank에 1을 더해준다.
두 분리 집합을 union할 경우, 자식이 되는 쪽의 parent 값들을 갱신해 주어야 하고 이 과정에서 깊이가 깊을 수록 시간이 더욱 소모되므로 두 집합의 rank를 비교하여 더 작은 쪽이 자식이 되도록 만들어 주면 소요되는 시간을 줄일 수 있다.
# (4) Union by rank
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
pa = find_parent(parent, a)
pb = find_parent(parent, b)
if pa != pb:
if rank[pa] < rank[pb]: parent[pa] = pb
else:
parent[pb] = pa
if rank[pa] == rank[pb]: rank[pa] += 1
import sys
n, m = map(int, sys.stdin.readline().split())
parent = [x for x in range(n+1)]
rank = [0 for x in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
union(parent, a, b)
for i in range(1,n+1): print(i, ":", find_parent(parent, i))