competitive/algorithm/
chromatic_number.rs

1use super::{MInt, MIntBase, One, Zero, binary_search};
2
3#[derive(Debug, Clone)]
4pub struct IndependentSubSet<M>
5where
6    M: MIntBase,
7{
8    pub n: usize,
9    pub ind: Vec<MInt<M>>,
10}
11
12impl<M> IndependentSubSet<M>
13where
14    M: MIntBase,
15{
16    pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self {
17        let mut g = vec![0; n];
18        for &(u, v) in edges {
19            g[u] |= 1 << v;
20            g[v] |= 1 << u;
21        }
22        Self::from_adj_graph(&g)
23    }
24
25    pub fn from_adj_graph(g: &[usize]) -> Self {
26        let n = g.len();
27        let mut ind = Vec::with_capacity(1 << n);
28        ind.push(MInt::one());
29        for s in 1usize..1 << n {
30            let v = s.trailing_zeros() as usize;
31            ind.push(ind[s - (1 << v)] + ind[s & !(g[v] | (1 << v))]);
32        }
33        Self { n, ind }
34    }
35
36    pub fn k_colorable(&self, k: usize) -> bool {
37        !self
38            .ind
39            .iter()
40            .map(|d| d.pow(k))
41            .enumerate()
42            .map(|(s, d)| if s.count_ones() % 2 == 0 { d } else { -d })
43            .sum::<MInt<M>>()
44            .is_zero()
45    }
46
47    /// The smallest number of colors needed to color a graph.
48    pub fn chromatic_number(&self) -> usize {
49        binary_search(|&k| self.k_colorable(k), self.n, 0)
50    }
51}
competitive/algorithm/chromatic_number.rs

competitive/algorithm/
chromatic_number.rs
