백준 20955 민서의 응급 수술 풀이 ( 파이썬 )
https://www.acmicpc.net/problem/20955
20955번: 민서의 응급 수술
민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서
www.acmicpc.net
이런 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)
[ baekjoon ] 소수상근수 9421번 ( python ) (0) | 2021.06.28 |
---|---|
[ baekjoon ] 골목 대장 호석 - 효율성2 20183번 ( python ) (0) | 2021.06.23 |
[ baekjoon ] 섬의 개수 4963번 ( python ) (0) | 2021.06.15 |
[ baekjoon ] 침투 13565번 ( python ) (0) | 2021.06.15 |
[ baekjoon ] 군사 이동 11085번 ( python ) (0) | 2021.06.08 |