[백준] 20040.사이클 게임 (C++)

20040. 사이클 게임

해설

문제를 해석하는데 많은 시간이 걸렸다... (이런 난독증)

쉽게 해설하면 아주 간단하다.
두 노드를 선택하여 이들을 잇는 간선을 매번마다 선택하는데
간선을 선택할 때 마다 사이클이 발생하는지 확인하는 문제이다.

Union&Find를 활용하여 매 선택된 간선마다 사이클 발생 여부를 확인하면 된다.
노드1의 find 값과 노드2의 find 값이 동일하다면 같은 집합에 속한다는 뜻으로,
이때는 수행을 현재 수행 번호를 출력하고 종료한다.

cf.) 만약 음의 간선을 통한 사이클이 발생한다면 벨만-포드 알고리즘을 이용한다.

구현