haar_lib/graph/
chromatic_number.rs

1//! グラフの彩色数
2//!
3//! # References
4//! - <https://www.slideshare.net/slideshow/ss-12131479/12131479>
5//!
6//! # Problems
7//! - <https://judge.yosupo.jp/problem/chromatic_number>
8use crate::{graph::*, math::mod_ops::pow::mod_pow};
9
10const M: u64 = 1000000007;
11
12/// グラフの彩色数を求める。
13pub fn chromatic_number<E: EdgeTrait>(graph: &Graph<Undirected, E>) -> usize {
14    let n = graph.len();
15
16    let mut g = vec![0; n];
17    for e in graph.nodes_iter().flatten() {
18        g[e.from()] |= 1 << e.to();
19    }
20
21    let mut f = vec![0_u64; 1 << n];
22    f[0] = 1;
23    for i in 1_usize..(1 << n) {
24        let c = i.trailing_zeros();
25        f[i] = f[i - (1 << c)] + f[(i - (1 << c)) & !g[c as usize]];
26        if f[i] >= M {
27            f[i] -= M;
28        }
29    }
30
31    let check = |k| {
32        let mut t = 0;
33
34        for (i, &f) in f.iter().enumerate() {
35            let s = mod_pow(f, k as u64, M);
36            if s == 0 {
37                continue;
38            }
39
40            if i.count_ones() % 2 == 1 {
41                t += M - s;
42            } else {
43                t += s;
44            }
45            if t >= M {
46                t -= M;
47            }
48        }
49
50        t % M != 0
51    };
52
53    for i in 1..n {
54        if check(i) {
55            return i;
56        }
57    }
58    n
59}
haar_lib/graph/chromatic_number.rs

haar_lib/graph/
chromatic_number.rs
