competitive/algorithm/
chromatic_number.rs

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

competitive/algorithm/chromatic_number.rs

competitive/algorithm/
chromatic_number.rs