strongly_connected_components/
lib.rs

1/// 強連結成分分解です。[参考](https://manabitimes.jp/math/1250)
2///
3/// 返り値を `components` とすると `components` の各要素は強連結成分をなす頂点のベクタです。
4pub fn strongly_connected_components(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
5    let mut graph = vec![vec![]; n];
6    for &(u, v) in edges {
7        graph[u].push(v);
8    }
9
10    let mut seen = vec![false; n];
11    let mut order = Vec::new();
12    let mut order_pushed = vec![false; n];
13    for v in 0..n {
14        if seen[v] {
15            continue;
16        }
17        let mut stack = Vec::new();
18        stack.push(v);
19        while let Some(x) = stack.pop() {
20            seen[x] = true;
21            stack.push(x);
22            let mut pushed = false;
23            for &y in &graph[x] {
24                if !seen[y] {
25                    stack.push(y);
26                    pushed = true;
27                }
28            }
29            if !pushed {
30                debug_assert_eq!(stack.last(), Some(&x));
31                stack.pop();
32                if !order_pushed[x] {
33                    order_pushed[x] = true;
34                    order.push(x);
35                }
36            }
37        }
38    }
39    assert_eq!(order.len(), n);
40
41    let mut rev_graph = vec![vec![]; n];
42    #[allow(clippy::needless_range_loop)]
43    for u in 0..n {
44        for &v in &graph[u] {
45            rev_graph[v].push(u);
46        }
47    }
48
49    let mut seen = vec![false; n];
50    let mut component_id = vec![0; n];
51    let mut id = 0;
52    for &v in order.iter().rev() {
53        if seen[v] {
54            continue;
55        }
56        let mut stack = Vec::new();
57        stack.push(v);
58        while let Some(x) = stack.pop() {
59            seen[x] = true;
60            component_id[x] = id;
61            for &y in &rev_graph[x] {
62                if !seen[y] {
63                    stack.push(y);
64                }
65            }
66        }
67        id += 1;
68    }
69
70    let mut components = vec![vec![]; id];
71    for v in 0..n {
72        components[component_id[v]].push(v);
73    }
74    components
75}
76
77#[cfg(test)]
78mod tests {
79    use crate::strongly_connected_components;
80
81    #[test]
82    fn test_single_node() {
83        let scc = strongly_connected_components(1, &[]);
84        assert_eq!(scc, vec![vec![0]]);
85    }
86
87    #[test]
88    fn test_small() {
89        // 0 -> 1
90        assert_eq!(
91            strongly_connected_components(2, &[(0, 1)]),
92            vec![vec![0], vec![1]]
93        );
94
95        // 0 -> 1
96        // 0 -> 1
97        assert_eq!(
98            strongly_connected_components(2, &[(0, 1), (0, 1)]),
99            vec![vec![0], vec![1]]
100        );
101
102        // 0 <-> 1
103        let mut scc = strongly_connected_components(2, &[(0, 1), (1, 0)]);
104        for com in &mut scc {
105            com.sort();
106        }
107        assert_eq!(scc, vec![vec![0, 1]]);
108    }
109}
strongly_connected_components/lib.rs

strongly_connected_components/
lib.rs
