[BOJ] 20955 - 민서의 응급 수술 (Python)

 

 

아이디어

 

유니온 파인드로 사이클이 발생하지 않도록 뉴런을 연결해 나간다.

 

 

풀이

 

두 뉴런이 이미 같은 집합에 포함되어 있다면 사이클이 발생하므로 연결을 끊는다.

 

import sys

input = sys.stdin.readline

def solution():

    def find(n):
        temp = n
        while n != group[n]:
            n = group[n]
        group[temp] = n
        return n

    def union(n1, n2):
        n1 = find(n1)
        n2 = find(n2)
        if n1 > n2:
            n1, n2 = n2, n1
        group[n2] = n1

    N, M = map(int, input().split())
    group = [i for i in range(N+1)]
    res = N-1
    for _ in range(M):
        u, v = map(int, input().split())
        if find(u) != find(v):
            union(u, v)
            res -= 1
        else:
            res += 1
    print(res)

solution()