[python] 백준 20955 민서의 응급 수술

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

20955번: 민서의 응급 수술

 

문제 해결

• 먼저 분리되어 있는 그룹이 몇개인지 알아야 한다. 그것을 유니온-파인드를 통해 알 수 있다.
• 만약 시냅스로 연결된 두 뉴런의 번호 u,v를 받았을 때 이미 같은 그룹에 있으면 더 연결 될 필요가 없으므로 잘라내는데에 연산을 한 번 쓰게 된다.
• 만약 다른 그룹이면 유니온-파인드를 통해 서로 연결 시킨다.
• 그룹이 다른 개수 + 이미 연결되어 연결 될 필요가 없는 개수를 합친다음 하나의 중심(그룹이 n개이면 1개를 중심으로 잇는 것을 하므로)을 빼면 정답이다.

 

CODE

import sys
input = sys.stdin.readline

def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]
def union(a,b):
    a = find(a)
    b = find(b)

    if a ==b:
        return
    
    if rank[a] > rank[b]:
        parents[b] = a
    elif rank[a] < rank[b]:
        parents[a] = b
    else:
        parents[a] = b
        rank[b] += 1

if __name__=='__main__':
    n, m = map(int, input().split())
    parents = [i for i in range(n+1)]
    rank = [0 for _ in range(n+1)]
    set_count = set() # 나뉘어져 있는 트리 개수
    cnt = 0
    for _ in range(m):
        u, v = map(int, input().split())
        if find(u)==find(v):
            cnt += 1
        else:
            union(u,v)
    for i in range(1,n+1):
        set_count.add(find(i))
    print(cnt+len(set_count)-1)