competitive_library/graph/
strongly_connected_component.rs

1#[derive(Debug)]
2enum Vertex {
3    In(usize),
4    Out(usize),
5}
6
7pub fn decompose(e: &[Vec<usize>]) -> Vec<Vec<usize>> {
8    let mut seen = vec![false; e.len()];
9
10    let mut stack = vec![];
11    let mut nodes = Vec::with_capacity(e.len());
12    for i in 0..e.len() {
13        if seen[i] {
14            continue;
15        }
16        stack.push(Vertex::In(i));
17
18        while let Some(vertex) = stack.pop() {
19            if let Vertex::In(v) = vertex {
20                if seen[v] {
21                    continue;
22                }
23                stack.push(Vertex::Out(v));
24                seen[v] = true;
25                for &to in e[v].iter() {
26                    stack.push(Vertex::In(to));
27                }
28            } else if let Vertex::Out(v) = vertex {
29                nodes.push(v);
30            }
31        }
32    }
33    let mut reverse_edge = vec![vec![]; e.len()];
34    for i in 0..e.len() {
35        for j in 0..e[i].len() {
36            reverse_edge[e[i][j]].push(i);
37        }
38    }
39
40    let mut components = vec![];
41    let mut back_stack = vec![];
42    let mut back_seen = vec![false; e.len()];
43    while let Some(v) = nodes.pop() {
44        if back_seen[v] {
45            continue;
46        }
47        let mut scc = vec![];
48        back_stack.push(v);
49        back_seen[v] = true;
50
51        while let Some(v) = back_stack.pop() {
52            for &to in reverse_edge[v].iter() {
53                if back_seen[to] {
54                    continue;
55                }
56                back_stack.push(to);
57                back_seen[to] = true;
58            }
59
60            scc.push(v);
61        }
62        components.push(scc);
63    }
64    components
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70    #[test]
71    fn test_scc() {
72        let n = 6;
73        let v = [(1, 4), (5, 2), (3, 0), (5, 5), (4, 1), (0, 3), (4, 2)];
74        let mut e = vec![vec![]; n];
75        for &(v, u) in v.iter() {
76            e[v].push(u);
77        }
78        let a = decompose(&e);
79        assertvv(&a, &[vec![5], vec![1, 4], vec![2], vec![0, 3]]);
80    }
81    #[test]
82    fn test_scc2() {
83        let n = 7;
84        let v = [
85            (0, 2),
86            (1, 2),
87            (2, 3),
88            (3, 2),
89            (3, 4),
90            (4, 5),
91            (5, 6),
92            (6, 4),
93        ];
94        let mut e = vec![vec![]; n];
95        for &(v, u) in v.iter() {
96            e[v].push(u);
97        }
98        let a = decompose(&e);
99        dbg!(&a);
100        assertvv(&a, &[vec![0], vec![1], vec![3, 2], vec![5, 6, 4]]);
101    }
102
103    #[test]
104    fn test_scc3() {
105        let n = 11;
106        let v = vec![
107            (0, 1),
108            (1, 2),
109            (1, 10),
110            (2, 0),
111            (2, 3),
112            (3, 4),
113            (4, 5),
114            (4, 10),
115            (5, 6),
116            (6, 3),
117            (7, 8),
118            (7, 9),
119            (8, 10),
120            (9, 7),
121            (9, 7),
122            (9, 7),
123            (9, 7),
124            (10, 7),
125        ];
126        let mut e = vec![vec![]; n];
127        for &(v, u) in v.iter() {
128            e[v].push(u);
129        }
130        let a = decompose(&e);
131        dbg!(&a);
132        assertvv(&a, &[vec![0, 1, 2], vec![3, 4, 5, 6], vec![7, 8, 9, 10]]);
133    }
134    #[test]
135    fn test_scc4() {
136        let n = 5;
137        let v = [(0, 1), (0, 2), (2, 3), (3, 4)];
138        let mut e = vec![vec![]; n];
139        for &(v, u) in v.iter() {
140            e[v].push(u);
141        }
142        let a = decompose(&e);
143        dbg!(&a);
144        assertvv(&a, &[vec![0], vec![1], vec![2], vec![3], vec![4]]);
145    }
146    #[test]
147    fn test_scc5() {
148        let n = 5;
149        let v = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)];
150        let mut e = vec![vec![]; n];
151        for &(v, u) in v.iter() {
152            e[v].push(u);
153        }
154        let a = decompose(&e);
155        dbg!(&a);
156        assertvv(&a, &[vec![0, 1, 2, 3, 4]]);
157    }
158    #[test]
159    fn test_scc6() {
160        let n = 6;
161        let v = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)];
162        let mut e = vec![vec![]; n];
163        for &(v, u) in v.iter() {
164            e[v].push(u);
165        }
166        let a = decompose(&e);
167        dbg!(&a);
168        assertvv(&a, &[vec![0, 1, 2, 3, 4], vec![5]]);
169    }
170    use std::collections::HashSet;
171    fn assertvv(a: &[Vec<usize>], b: &[Vec<usize>]) -> Option<()> {
172        assert_eq!(a.len(), b.len());
173        let mut a = convert(a);
174        let mut b = convert(b);
175
176        for i in a.iter_mut() {
177            for j in b.iter_mut() {
178                if j.is_none() {
179                    continue;
180                }
181                if i.as_ref()?.eq(j.as_ref()?) {
182                    i.take();
183                    j.take();
184                    break;
185                }
186            }
187            assert!(i.is_none());
188        }
189        Some(())
190    }
191    fn convert(a: &[Vec<usize>]) -> Vec<Option<HashSet<usize>>> {
192        a.iter()
193            .map(|x| Some(x.iter().cloned().collect::<HashSet<_>>()))
194            .collect::<Vec<_>>()
195    }
196}
competitive_library/graph/strongly_connected_component.rs

competitive_library/graph/
strongly_connected_component.rs
