[BOJ] 17434 도로 청소

문제 링크: [BOJ 17434](https://www.acmicpc.net/problem/17434)

문제 요약

무방향 그래프가 있다. 교집합이 없고 방문하는 간선의 합집합이 그래프 간선 전체인 오일러 투어 2개를 구하여라.

풀이

풀이 방향을 잘못 잡으면 구데기같은 구현에 고통받게 된다.

일단 가장 먼저 생각해야 하는 건, 그래프의 홀수 차수 점 개수는 반드시 0, 2, 4중 하나여야한다는 것이다. 오일러 투어를 하나 구하고 그 간선들을 모두 제거한다고 생각해보자. 그러면 오일러 순환인 경우 홀수 차수 점 개수는 그대로고 아니라면 2개 줄어든다. 모두 지웠을 때 개수가 0이어야 하므로 이 셋 중 하나이다.

홀수점 0개

아무 오일러 순환을 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 만든다.

홀수점 2개

아무 오일러 투어를 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 만든다.

홀수점 4개

오일러 투어 문제에서 자주 사용하는 테크닉인, 가상 간선을 사용해 보자. 홀수점 중 아무거나 뽑은 두 개가 A와 B라고 하면, A와 B를 잇는 가상의 간선을 하나 긋는다. 그러면 남은 홀수점이 2개가 되어서 오일러 투어를 하나 찾을 수 있다. 이 오일러 투어에는 간선 AB가 포함되어 있으므로, 이걸 기준으로 끊으면 오일러 투어 2개가 나온다.

소스코드

https://www.acmicpc.net/source/share/6d1184bc8970470d993bf5819499ce11