cp_library_rs/graph/
simple_graph.rs

1//! 単純グラフの連結成分分解，2部グラフ判定など
2
3type Graph = Vec<Vec<usize>>;
4
5/// # 単純グラフ
6/// 単純グラフに対して
7/// - 連結成分分解
8/// - 2部グラフ分解
9///
10/// を行う。
11#[derive(Debug)]
12pub struct SimpleGraph {
13    pub V: usize,
14    pub E: usize,
15    pub graph: Graph,
16    pub edges: Vec<(usize, usize)>,
17    pub component_size: Option<usize>,
18    pub components: Vec<usize>,
19}
20
21impl SimpleGraph {
22    const INF: usize = 1_000_000_000_000_000_000;
23
24    /// グラフの構築
25    pub fn new(V: usize) -> Self {
26        Self {
27            V,
28            E: 0,
29            graph: vec![vec![]; V],
30            edges: vec![],
31            component_size: None,
32            components: vec![Self::INF; V],
33        }
34    }
35
36    /// 辺の追加
37    pub fn add_edge(&mut self, u: usize, v: usize) {
38        self.E += 1;
39        self.edges.push((u, v));
40        self.graph[u].push(v);
41        self.graph[v].push(u);
42    }
43
44    /// 連結成分に分解：O(|V|+|E|)
45    pub fn decompose(&mut self) {
46        let mut component = 0;
47        self.components = vec![Self::INF; self.V];
48        for i in 0..self.V {
49            if self.components[i] != Self::INF {
50                continue;
51            }
52            self.components[i] = component;
53            let mut stack = vec![i];
54            while let Some(u) = stack.pop() {
55                for &v in &self.graph[u] {
56                    if self.components[v] == Self::INF {
57                        self.components[v] = component;
58                        stack.push(v);
59                    }
60                }
61            }
62            component += 1;
63        }
64        self.component_size = Some(component);
65    }
66
67    /// 2部グラフ判定：O(|V|+|E|)
68    pub fn bipartite(&mut self) -> Option<Vec<isize>> {
69        // 未だ連結成分分解されていない場合
70        if self.component_size.is_none() {
71            self.decompose();
72        }
73        let mut res: Vec<isize> = vec![0; self.V];
74        for i in 0..self.V {
75            let mut stack = vec![i];
76            if res[i] != 0 {
77                continue;
78            }
79            res[i] = self.components[i] as isize + 1;
80            while let Some(u) = stack.pop() {
81                for &v in &self.graph[u] {
82                    if res[v] == res[u] {
83                        return None;
84                    }
85                    if res[v] == 0 {
86                        res[v] = -res[u];
87                        stack.push(v);
88                    }
89                }
90            }
91        }
92        Some(res)
93    }
94}
cp_library_rs/graph/simple_graph.rs

cp_library_rs/graph/
simple_graph.rs
