scc/
lib.rs

1pub struct Scc<V, I> {
2    comp_id: Vec<usize>,
3    comp: Vec<Vec<V>>,
4    index: I,
5}
6
7impl<V, I> Scc<V, I>
8where
9    V: Eq + Clone,
10    I: Fn(&V) -> usize + Copy,
11{
12    pub fn new<D, J>(
13        vertices: impl Iterator<Item = V>,
14        len: usize,
15        index: I,
16        delta: D,
17    ) -> Self
18    where
19        D: Fn(&V) -> J + Copy,
20        I: Fn(&V) -> usize + Copy,
21        J: Iterator<Item = V>,
22    {
23        struct State {
24            scc: Vec<Vec<usize>>,
25            num: Vec<usize>,
26            low: Vec<usize>,
27            stack: Vec<usize>,
28            is_ancestor: Vec<bool>,
29            index: usize,
30        }
31
32        fn dfs<V, D, I, J>(v: &V, index: I, delta: D, state: &mut State)
33        where
34            D: Fn(&V) -> J + Copy,
35            I: Fn(&V) -> usize + Copy,
36            J: Iterator<Item = V>,
37        {
38            state.index += 1;
39            let vi = index(v);
40            state.low[vi] = state.index;
41            state.num[vi] = state.index;
42            state.stack.push(vi);
43            state.is_ancestor[vi] = true;
44            for nv in delta(v) {
45                let nvi = index(&nv);
46                if state.num[nvi] == 0 {
47                    dfs(&nv, index, delta, state);
48                    state.low[vi] = state.low[vi].min(state.low[nvi]);
49                } else if state.is_ancestor[nvi] {
50                    state.low[vi] = state.low[vi].min(state.num[nvi]);
51                }
52            }
53            if state.low[vi] == state.num[vi] {
54                let mut tmp = vec![];
55                loop {
56                    let nvi = state.stack.pop().unwrap();
57                    state.is_ancestor[nvi] = false;
58                    tmp.push(nvi);
59                    if vi == nvi {
60                        break;
61                    }
62                }
63                state.scc.push(tmp);
64            }
65        }
66
67        let mut state = State {
68            scc: vec![],
69            num: vec![0; len],
70            low: vec![0; len],
71            stack: vec![],
72            is_ancestor: vec![false; len],
73            index: 0,
74        };
75
76        let mut vs = vec![];
77        for v in vertices {
78            if state.num[index(&v)] == 0 {
79                dfs(&v, index, delta, &mut state);
80            }
81            vs.push(v);
82        }
83
84        let mut comp_id = vec![0; len];
85        for i in 0..state.scc.len() {
86            for &c in &state.scc[i] {
87                comp_id[c] = state.scc.len() - i - 1;
88            }
89        }
90
91        let mut comp: Vec<_> = (0..state.scc.len()).map(|_| vec![]).collect();
92        for v in vs {
93            comp[comp_id[index(&v)]].push(v);
94        }
95
96        Self { comp_id, comp, index }
97    }
98
99    pub fn comp_id(&self, v: &V) -> usize { self.comp_id[(self.index)(v)] }
100    pub fn comp(&self, i: usize) -> &[V] { &self.comp[i] }
101}
102
103#[cfg(test)]
104mod tests {
105    use crate::*;
106
107    #[test]
108    fn sanity_check() {
109        // 4 -> 0 <> 1 -> 5
110        //      |    ^
111        //      v    |
112        //      3 -> 2
113        //      ^
114        //      |
115        //      6
116        let g = vec![
117            vec![1, 3], // 0
118            vec![0, 5], // 1
119            vec![0],    // 2
120            vec![2],    // 3
121            vec![0],    // 4
122            vec![],     // 5
123            vec![3],    // 6
124        ];
125        let len = g.len();
126        let index = |&v: &usize| v;
127        let delta = |&v: &usize| g[v].iter().copied();
128        let scc = Scc::new(0..len, len, index, delta);
129
130        assert!(scc.comp_id(&0) == scc.comp_id(&1));
131        assert!(scc.comp_id(&0) == scc.comp_id(&2));
132        assert!(scc.comp_id(&0) == scc.comp_id(&3));
133        assert!(scc.comp_id(&0) > scc.comp_id(&4));
134        assert!(scc.comp_id(&0) > scc.comp_id(&6));
135        assert!(scc.comp_id(&0) < scc.comp_id(&5));
136    }
137}
scc/lib.rs

scc/
lib.rs
