[python] union 연산으로 노드 집합 관계 구하기

from sys import stdin
n,m = map(int, stdin.readline().split())
parent = [0]*(n+1)
def find_parent(a):
    if a != parent[a]:
        parent[a] = find_parent(parent[a])
        
    return  parent[a]

def union_parent(a,b):
    pa = find_parent(a)
    pb = find_parent(b)
    if pa > pb:
        parent[a] = b
    else:
        parent[b] = a
        
for i in range(1,n+1):
    parent[i] = i

for i in range(n):
    li = list(map(int,stdin.readline().split()))
    for j in range(n):
        if li[j] == 1:
            union_parent(i+1,j+1)
plan = list(map(int,stdin.readline().split()))
res = True

for i in range(m-1):
    if find_parent(i) != find_parent(i+1):
        res = False
        break

if res:
    print("True")
else:
    print("False")

 

 

n = 노드 수, m= 여행하려는 노드 수

 

parent[idx] = idx 번 노드의 부모 노드

 

 

출처: 동빈북