fn select_vertex(cand: usize, deg: &[u32], sat: &[usize]) -> usizeExamples found in repository?
crates/competitive/src/algorithm/chromatic_number.rs (line 40)
34fn greedy_coloring(g: &[usize], deg: &[u32]) -> usize {
35 let n = g.len();
36 let mut rem = (1usize << n) - 1;
37 let mut sat = vec![0usize; n];
38 let mut used = 0;
39 while rem != 0 {
40 let v = select_vertex(rem, deg, &sat);
41 let c = (!sat[v]).trailing_zeros() as usize;
42 used = used.max(c + 1);
43 rem &= !(1 << v);
44 let mut next = g[v] & rem;
45 while next != 0 {
46 let u = next.trailing_zeros() as usize;
47 next &= next - 1;
48 sat[u] |= 1 << c;
49 }
50 }
51 used
52}
53
54fn search_coloring(
55 g: &[usize],
56 deg: &[u32],
57 sat: &mut [usize],
58 rem: usize,
59 used: usize,
60 best: &mut usize,
61) {
62 if rem == 0 {
63 *best = used;
64 return;
65 }
66 if used >= *best {
67 return;
68 }
69 let v = select_vertex(rem, deg, sat);
70 let rem = rem & !(1 << v);
71 let mut colors = ((1 << used) - 1) & !sat[v];
72 if used + 1 < *best {
73 colors |= 1 << used;
74 }
75 while colors != 0 {
76 let color = colors & colors.wrapping_neg();
77 colors ^= color;
78 let mut next = g[v] & rem;
79 let mut changed = 0usize;
80 while next != 0 {
81 let u = next.trailing_zeros() as usize;
82 next &= next - 1;
83 if sat[u] & color == 0 {
84 sat[u] |= color;
85 changed |= 1 << u;
86 }
87 }
88 search_coloring(
89 g,
90 deg,
91 sat,
92 rem,
93 used.max(color.trailing_zeros() as usize + 1),
94 best,
95 );
96 while changed != 0 {
97 let u = changed.trailing_zeros() as usize;
98 changed &= changed - 1;
99 sat[u] ^= color;
100 }
101 }
102}