오일러의 순환 도시
다이아몬드 II의견: 0
\(N\)개의 정점과 \(M\)개의 방향 간선으로 이루어진 방향 그래프가 주어진다. 간선은 중복될 수 있다 (같은 두 정점 사이에 같은 방향의 간선이 여러 개 있을 수 있다). 단, 자기 자신으로 가는 간선(자기 루프)은 없다.
오일러 회로란 그래프의 모든 간선을 정확히 한 번씩 지나 출발한 정점으로 되돌아오는 닫힌 경로를 말한다.
간선들은 입력에 주어진 순서대로 \(1\)번부터 \(M\)번까지 번호가 매겨져 있으며, 같은 두 정점 사이의 여러 간선은 서로 다른 것으로 구별한다. 우리는 \(1\)번 간선으로 시작하는 오일러 회로의 개수를 센다. 즉, \(e_1 e_2 \dots e_M\) 형태의 간선 수열로서 \(e_1\)이 \(1\)번 간선이고, 모든 간선을 한 번씩 사용하며, 이전 간선의 도착점이 다음 간선의 출발점과 같고, 마지막 간선의 도착점이 \(1\)번 간선의 출발점인 수열의 개수를 구한다.
그러한 오일러 회로가 하나도 없으면 \(0\)을 출력한다. 답이 매우 클 수 있으므로 \(998244353\)으로 나눈 나머지를 출력하라.
\(1 \le N \le 300\)
\(1 \le M \le 4000\)
\(1 \le u, v \le N\), \(u \ne v\)
그래프에는 다중 간선이 존재할 수 있으나 자기 루프는 없다.
첫 줄에 정점 수 \(N\)과 간선 수 \(M\)이 주어진다.
이어지는 \(M\)개의 줄에 각 간선의 출발 정점 \(u\)와 도착 정점 \(v\)가 주어진다 (\(1 \le u, v \le N\)). 이 순서가 곧 간선 번호이다.
\(1\)번 간선으로 시작하는 오일러 회로의 개수를 \(998244353\)으로 나눈 나머지로 한 줄에 출력한다.
3 3
1 2
2 3
3 1
1간선: 1:(1->2), 2:(2->3), 3:(3->1). 1번 간선으로 시작하는 오일러 회로는 1->2->3->1 단 하나뿐이므로 답은 1.
3 4
1 2
2 1
1 3
3 1
1간선: 1:(1->2),2:(2->1),3:(1->3),4:(3->1). 정점 1에서 두 개의 작은 고리가 갈라진다. 1번 간선으로 시작: 1->2->1->3->1 한 가지뿐이므로 답은 1. (BEST 정리: 어보레슨스 수 \(\times \prod (\deg-1)! = 1 \times 1! \times 0! \times 0! = 1\).)
riseoj 작성
출처 Original
평가 및 의견
오일러의 순환 도시
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
오일러의 순환 도시