[백준] 14940 쉬운 최단거리(파이썬/python)

🎈문제

https://www.acmicpc.net/problem/20955

 

🎁어떤 알고리즘?

1. union-find 알고리즘

💻코드

# 20955 민서의 응급 수술

# import sys

# input = sys.stdin.readline

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

def union(a,b):
    ra = find(a)
    rb = find(b)
    parent[ra] = parent[rb] = min(ra,rb)

# 1. 입력
n,m = map(int,input().split())
parent = [i for i in range(n+1)]
cnt = 0

for _ in range(m):
    u,v = map(int,input().split())

    if find(u) == find(v):  # 부모가 같으면 싸이클
        cnt += 1
    else:   # 싸이클이 없으면 union
        union(u,v)

# 떨어진 노드 최상위 노드에 연결
for i in range(1,n+1):
    if find(i-1) != find(i):
        union(i-1,i)
        cnt += 1

print(cnt-1)

🎄코드 설명

1. 부모(최상위 노드)가 같으면 싸이클이 되므로 트리가 되기 위해 연결을 끊어줘야 한다. 따라서 cnt + 1

2. 부모가 같지 않으면 싸이클이 아니므로 부모 노드만 찾아놓는다.

3. for문을 한번 더 돌려서 부모 노드가 다른 트리들을 하나의 트리로 이어준다. 이때, 이어준 개수만큼 cnt + 1