library_checker/graph/counting_spanning_tree_undirected.rs
1use competitive::prelude::*;
2use competitive::{algebra::AddMulOperation, math::Matrix, num::mint_basic::MInt998244353 as M};
3
4#[verify::library_checker("counting_spanning_tree_undirected")]
5pub fn counting_spanning_tree_undirected(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, m, edges: [(usize, usize); iter m]);
8 let mut a = Matrix::<AddMulOperation<M>>::zeros((n - 1, n - 1));
9 for (u, v) in edges {
10 if u < n - 1 {
11 a[u][u] += M::from(1);
12 }
13 if v < n - 1 {
14 a[v][v] += M::from(1);
15 }
16 if u < n - 1 && v < n - 1 {
17 a[u][v] -= M::from(1);
18 a[v][u] -= M::from(1);
19 }
20 }
21 pp!(a.determinant());
22}