[이취코-그래프 이론] 개선된 서로소 집합 알고리즘 소스코드 / Python

입력 예시

6 4 # 노드와 간선의 개수

1 4 # 노드와 노드 사이의 연결 관계

2 3

2 4

5 6

 

출력 예시

각 원소가 속한 집합: 1 1 1 1 5 5

부모 테이블: 1 1 1 1 5 5

 

import sys

input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


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


v, e = map(int, input().split())
parent = [i for i in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print("각 원소가 속한 집합: ", end="")
for i in range(1, v + 1):
    print(find_parent(parent, i), end=" ")

print()

print("부모 테이블: ", end="")
for i in range(1, v + 1):
    print(parent[i], end=" ")