haar_lib/graph/
max_independent_set.rs

1//! 最大独立集合
2//!
3//! # Verifications
4//! - [Maximum Independent Set](https://judge.yosupo.jp/problem/maximum_independent_set) [#142761](https://judge.yosupo.jp/submission/142761) (n <= 40)
5use crate::graph::*;
6use std::collections::HashSet;
7
8/// 最大独立集合を求める
9///
10/// nは64以下に制限している。
11/// 最大独立集合の補集合は最小頂点被覆集合になる。
12pub fn max_independent_set<E: EdgeTrait>(g: &Graph<Undirected, E>) -> Vec<usize> {
13    let n = g.len();
14    assert!(n <= 64);
15
16    let mut set = HashSet::new();
17    rec(g, 0, 0, &mut set);
18
19    let (a, _) = set
20        .into_iter()
21        .filter(|(indep, cover)| (indep | cover).count_ones() as usize == n)
22        .max_by_key(|&(indep, _)| indep.count_ones())
23        .unwrap();
24
25    (0..n).filter(|i| a & (1 << i) != 0).collect()
26}
27
28fn rec<E: EdgeTrait>(
29    g: &Graph<Undirected, E>,
30    indep: u64,
31    cover: u64,
32    set: &mut HashSet<(u64, u64)>,
33) {
34    if set.contains(&(indep, cover)) {
35        return;
36    }
37
38    set.insert((indep, cover));
39
40    let removed = indep | cover;
41
42    let next = (0..g.len())
43        .filter(|i| removed & (1 << i) == 0)
44        .max_by_key(|&i| {
45            g.nodes[i]
46                .edges
47                .iter()
48                .filter(|e| removed & (1 << e.to()) == 0)
49                .count()
50        });
51
52    let Some(next) = next else { return };
53
54    let mut deg = 0;
55    let mut neighbour: u64 = 0;
56
57    for e in g.nodes[next].edges.iter() {
58        if removed & (1 << e.to()) == 0 {
59            deg += 1;
60            neighbour |= 1 << e.to();
61        }
62    }
63
64    rec(g, indep | (1 << next), cover | neighbour, set);
65    if deg > 1 {
66        rec(g, indep, cover | (1 << next), set);
67    }
68}
haar_lib/graph/max_independent_set.rs

haar_lib/graph/
max_independent_set.rs
