Skip to main content

greedy_coloring

competitive::algorithm::chromatic_number

Function greedy_coloring 

Source 
fn greedy_coloring(g: &[usize], deg: &[u32]) -> usize
Examples found in repository?
crates/competitive/src/algorithm/chromatic_number.rs (line 13)
2pub fn chromatic_number(n: usize, edges: &[(usize, usize)]) -> usize {
3    assert!(n < usize::BITS as usize);
4    if n == 0 {
5        return 0;
6    }
7    let mut g = vec![0usize; n];
8    for &(u, v) in edges {
9        g[u] |= 1 << v;
10        g[v] |= 1 << u;
11    }
12    let deg: Vec<_> = g.iter().map(|g| g.count_ones()).collect();
13    let mut best = greedy_coloring(&g, &deg);
14    search_coloring(&g, &deg, &mut vec![0; n], (1 << n) - 1, 0, &mut best);
15    best
16}