[16168] 퍼레이드

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

16168번: 퍼레이드

유니온 파인드 문제다. 오일러 경로를 이용해야 한다.

 

풀이

문제에서 주어지는 것은 모든 간선을 한 번에 이용하면서 모든 노드의 순회가 가능하냐는 것이다. 즉 주어진 도형을 한 손 그리기가 가능하냐로 생각이 가능하다. 

이에 관한 공식이 있는지 찾아보았는데, '오일러 경로'에 대한 자료를 찾을 수 있었다. 각 노드의 진입, 진출 차수의 합이 짝수이면 한붓그리기가 가능하며, 예외적으로 차수가 홀수인 것이 2개라면 한붓 그리기가 가능하다고 한다.

차수가 홀수인 것이 0개 또는 2개라면 한붓그리기가 가능하다

따라서 문제에서 요구하는 것을 요약하자면, 모든 정점이 하나의 컴포넌트인지, 그렇다면 각 노드의 차수가 홀수인 경우가 0 또는 2라면 해당 그래프는 퍼레이드가 가능한 그래프인 것으로 출력하면 된다.

 

정답 코드