백준 20955 : 민서의 응급 수술 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)


def Find(x):
    if disjoint[x]!=x:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a==b:
        return False

    else:
        if a>b:
            disjoint[a]=b
        else:
            disjoint[b]=a
        return True

N,M=map(int,input().split())

disjoint=[0]*(N+1) ; total=0
for i in range(1,N+1):
    disjoint[i]=i

for i in range(M):
    a,b=map(int,input().split())

    if not Union(a,b):
        total+=1

for i in range(1,N+1):
    if Find(i-1)!=Find(i):
        Union(i-1,i)
        total+=1

print(total-1)

📌 어떻게 접근할 것인가?

유니온 파인드를 통해 풀었습니다.

먼저 문제에서는 뉴런들을 붙이거나 잘라서 사이클없는 트리를 만드는 것이 목표입니다.

일단 먼저 문제에서 주어지는 뉴런의 연결 요소들을 유니온 파인드를 통해 연결해줍니다.
이때 사이클이 없어야 하므로 Find(a) 와 Find(b) 가 다를때만 연결합니다.

그렇다면 유니온 파인드만 실행한다면 위 그럼처럼 서로 집합들이 연결되어있다고 볼수 있습니다.
하지만 문제에서는 모든 뉴런을 연결해야하므로

모든 노드들의 최상위 노드가 같아야 합니다.

다만 유니온파인드를 사용할때 이미 사이클이 없도록 연결했으므로

3 과 7 같은 노드들은 바로 1에 연결해주면 됩니다.