[20955] 민서의 응급 수술

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

20955번: 민서의 응급 수술

유니온 파인드 문제다. 문제의 내용만 잘 이해한다면 쉽게 풀 수 있는 문제다.

 

풀이

문제에서 요구하는 것은 모든 뉴럴들을 사이클이 없는 하나의 그래프로 만들려면 몇 번의 연산이 필요한지 구하는 것이다. 역으로 생각하면 주어진 뉴럴들의 연결 상태에서 사이클이 몇 번 일어나는지, 그리고 컴포넌트의 개수를 합산하여 출력하면 된다. 

사이클이 일어난다는 것은 주어진 두 뉴럴의 루트가 같다는 것. 즉 유니온이 일어날 때, 두 노드의 루트를 확인하는데, 이때 루트가 같다면 연결을 끊어내는 작업을 해야 하므로 연산 횟수 1 증가.

최종 컴포넌트의 상태를 확인할 때, 컴포넌트가 2개 이상이라면 하나로 합치는 연산을 수행하므로 (총 컴포넌트 개수 - 1) 횟수를 추가하여 출력하면 된다.

 

정답 코드