Skip to main content

library_checker/graph/
counting_eulerian_circuits.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::AddMulOperation,
4    math::{Matrix, MemorizedFactorial},
5    num::{One, mint_basic::MInt998244353 as M},
6};
7
8#[verify::library_checker("counting_eulerian_circuits")]
9pub fn counting_eulerian_circuits(reader: impl Read, writer: impl Write) {
10    prepare_io!(reader, writer);
11    sc!(n, m, edges: [(usize, usize); iter m]);
12    let mut a = Matrix::<AddMulOperation<M>>::zeros((n, n));
13    let mut indegree = vec![0; n];
14    let mut outdegree = vec![0; n];
15    for (u, v) in edges {
16        a[u][v] -= M::from(1);
17        a[v][v] += M::from(1);
18        outdegree[u] += 1;
19        indegree[v] += 1;
20    }
21    if indegree != outdegree {
22        pp!(0);
23        return;
24    }
25    let root = outdegree.iter().position(|&d| d != 0).unwrap();
26    for i in 0..n {
27        a[root][i] = M::from(0);
28        a[i][root] = M::from(0);
29        if outdegree[i] == 0 {
30            a[i][i] = M::one();
31        }
32    }
33    a[root][root] = M::one();
34    let factorial = MemorizedFactorial::new(*outdegree.iter().max().unwrap() - 1);
35    let mut ans = a.determinant();
36    for d in outdegree {
37        if d != 0 {
38            ans *= factorial.fact[d - 1];
39        }
40    }
41    pp!(ans);
42}