[ baekjoon ] 민서의 응급 수술 20955번 ( python )

문제

백준 20955 민서의 응급 수술 풀이 ( 파이썬 )

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

20955번: 민서의 응급 수술

 

풀이

이런 3개의 집합들을 연결하기 전에 사이클이 있는지 확인한 후에 사이클이 있는 집합에서 한 선만 제거하면 사이클이 사라지게 되므로 사이클이 있을 때 cnt를 하나씩 증가시킨다.(cnt만큼 제거 된다고 치는 것)

그리고 이제 한 노드씩 확인해서 부모가 다르다면 union 해주고 연결된 선(link)를 하나씩 증가시킨다.

예시를 정답으로 만들었을 때 위의 그림이다.

import sys

input=sys.stdin.readline

m,n=map(int,input().split())

parent=list(range(m+1))

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

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

cnt=0

for i in range(n):
    st,ed=map(int,input().split())
    # union 하기 전인데 부모가 같다면 싸이클이 존재한다는 것
    if find_parent(parent,st)==find_parent(parent,ed):
        cnt+=1
    union_parent(parent,st,ed)
    
link=0
for i in range(1,m):
    if find_parent(parent,i)!=find_parent(parent,i+1):
        union_parent(parent,i,i+1)
        link+=1

print(cnt+link)