haar_lib/graph/
scc.rs

1//! 強連結成分分解
2
3use crate::graph::*;
4
5/// 強連結成分分解
6pub struct SCC {
7    groups: Vec<Vec<usize>>,
8    index: Vec<usize>,
9}
10
11impl SCC {
12    /// グラフから[`SCC`]を構築する。
13    ///
14    /// **Time complexity** $O(V + E)$
15    pub fn new<E: EdgeTrait>(g: &Graph<Directed, E>) -> Self {
16        let n = g.len();
17
18        let mut check = vec![false; n];
19        let mut ord = Vec::with_capacity(n);
20        for i in 0..n {
21            if !check[i] {
22                Self::dfs(g, i, &mut ord, &mut check);
23            }
24        }
25        ord.reverse();
26
27        let mut rg = vec![vec![]; n];
28        for e in g.nodes_iter().flat_map(|v| &v.edges) {
29            rg[e.to()].push(e.from());
30        }
31
32        let mut groups = vec![];
33        let mut check = vec![false; n];
34
35        let mut stack: Vec<usize> = Vec::with_capacity(n);
36
37        for u in ord {
38            if !check[u] {
39                let mut temp = vec![];
40                stack.push(u);
41                while let Some(cur) = stack.pop() {
42                    check[cur] = true;
43                    for &to in &rg[cur] {
44                        if !check[to] {
45                            stack.push(to);
46                        }
47                    }
48                    temp.push(cur);
49                }
50                groups.push(temp);
51            }
52        }
53
54        let mut index = vec![0; n];
55        for (i, s) in groups.iter().enumerate() {
56            for &x in s {
57                index[x] = i;
58            }
59        }
60
61        Self { groups, index }
62    }
63
64    fn dfs<E: EdgeTrait>(
65        g: &Graph<Directed, E>,
66        cur: usize,
67        ord: &mut Vec<usize>,
68        check: &mut [bool],
69    ) {
70        check[cur] = true;
71        for e in g.nodes[cur].edges.iter() {
72            if !check[e.to()] {
73                Self::dfs(g, e.to(), ord, check);
74            }
75        }
76
77        ord.push(cur);
78    }
79
80    /// 強連結成分を返す。
81    pub fn groups(&self) -> &Vec<Vec<usize>> {
82        &self.groups
83    }
84
85    /// 頂点がどのグループに属しているかを示した`Vec`への参照を返す。
86    pub fn index(&self) -> &Vec<usize> {
87        &self.index
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test() {
97        // https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_3_C
98
99        let mut g = Graph::<Directed, _>::new(5);
100        g.extend(
101            vec![(0, 1), (1, 0), (1, 2), (2, 4), (4, 3), (3, 2)]
102                .into_iter()
103                .map(|(u, v)| Edge::new(u, v, (), ())),
104        );
105        let scc = SCC::new(&g);
106        let scc = scc.index();
107
108        assert_eq!(scc[0], scc[1]);
109        assert_ne!(scc[0], scc[3]);
110        assert_eq!(scc[2], scc[3]);
111        assert_eq!(scc[3], scc[4]);
112    }
113}
haar_lib/graph/scc.rs

haar_lib/graph/
scc.rs
