유적지 여행

유적지 여행

유근이는 N개의 도시와 M개의 도로로 연결된 유적지를 여행하려고 한다. 유근이는 사실 도시를 방문하는 것 보다 드라이브하는 것에 더 관심이 많아서 N개의 도시를 모두 방문하지 못하더라도 M개의 도로를 모두 지나가길 원한다. 다만 유근이는 M개의 도로 중 2개의 도로는 한번씩만 지나고, 나머지 M-2개의 도로는 정확히 2번씩 방문하는 여행루트를 만들려 한다. 도로로 연결되어있지 않은 곳은 서로 이동할 수 없기 때문에 한 번 여행을 시작하면 시작점과 연결된 도시들만 여행할 수 있다. 또한 여행 루트에서 출발지와 목적지 도시는 중요하지 않고, 어떤 도로를 한번씩만 지나는지, 어떤 도로를 두 번씩 지나는지에 따라 각기 다른 루트로 간주한다고 한다.  유근이가 모든 M개의 도로를 여행할 수 있는 여행루트의 개수를 구하는 프로그램을 작성하시오.

[제약조건]

도로는 서로 다른 도시를 연결하는 경우도 있지만, 다른 도시가 아닌 자기 자신으로 연결된 도로도 존재한다.임의의 두 도시를 연결하는 도로는 최대 한번만 주어진다. 즉, 같은 마을들을 연결하는 도로가 두 번 주어지는 경우는 없다.

---

먼저 도로가 연결된 도시가 있으면, 그 지점부터 DFS로 모든 도로가 연결되어있는지 부터 판단한다.

만약 하나의 도로라도 연결되지 않은 것이 있다면 당연히 경우의수는 0이된다.

모든 도로를 방문할 수 있다면, 2개의 간선은 한번씩만 지나야 하므로 어떤 형태로 두개의 간선이 선택되어야 하는지를 살펴봐야 한다.

먼저, 두개의 간선이 모두 self-loop인 경우 모든 노드는 짝수점이 되기때문에 한붓그리기가 가능하다.

두개의 간선중 하나가 self-loop인 경우, self-loop이 아닌간선의 양쪽 노드만 홀수점이기 때문에 이 역시 한붓그리기가 가능하다.

마지막으로 두개의 간선이 모두 self-loop가 아닐 때를 살펴보자.

두개의 간선이 서로 떨어져 있다면 두개 간선의 양쪽 노드, 즉, 4개의 노드는 홀수점이 되기 때문에 한붓그리기가 불가능하다.

반면 두개의 간선이 맞닿아있다면 두개의 간선이 모두 가리키는 노드를 제외한 양쪽 노드만 홀수점이 되기 때문에 한붓그리기가 가능하다.

따라서 self-loop의 개수를 K라 하면,

 

으로 답을 구할 수 있다.