competitive_programming_rs/graph/
strongly_connected_components.rs

1pub mod strongly_connected_components {
2    use std::collections::VecDeque;
3
4    pub fn decompose(graph: &[Vec<usize>]) -> Vec<usize> {
5        let mut vs = Vec::new();
6        let num_v = graph.len();
7        let mut cmp = vec![0; num_v];
8
9        let mut reverse_graph = vec![vec![]; num_v];
10
11        for (i, edges) in graph.iter().enumerate() {
12            for &v in edges.iter() {
13                reverse_graph[v].push(i);
14            }
15        }
16        let mut used = vec![false; num_v];
17
18        let mut stack = VecDeque::new();
19        let mut added = vec![false; num_v];
20        for i in 0..num_v {
21            if used[i] {
22                continue;
23            }
24            stack.push_front(i);
25            while let Some(v) = stack.pop_front() {
26                stack.push_front(v);
27                used[v] = true;
28                let mut pushed = false;
29                for &u in graph[v].iter().rev() {
30                    if !used[u] {
31                        stack.push_front(u);
32                        pushed = true;
33                    }
34                }
35                if !pushed {
36                    stack.pop_front();
37                    if !added[v] {
38                        vs.push(v);
39                        added[v] = true;
40                    }
41                }
42            }
43        }
44
45        used = vec![false; num_v];
46        let mut k = 0;
47        vs.reverse();
48        for &i in vs.iter() {
49            if used[i] {
50                continue;
51            }
52            stack.push_front(i);
53            used[i] = true;
54            cmp[i] = k;
55            while let Some(v) = stack.pop_front() {
56                stack.push_front(v);
57                let mut pushed = false;
58                for &u in reverse_graph[v].iter() {
59                    if used[u] {
60                        continue;
61                    }
62                    used[u] = true;
63                    cmp[u] = k;
64                    stack.push_front(u);
65                    pushed = true;
66                }
67                if !pushed {
68                    stack.pop_front();
69                }
70            }
71            k += 1;
72        }
73
74        cmp
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use crate::utils::test_helper::Tester;
82
83    #[test]
84    fn solve_grl_3_c() {
85        let tester = Tester::new("./assets/GRL_3_C/in/", "./assets/GRL_3_C/out/");
86        tester.test_solution(|sc| {
87            let v: usize = sc.read();
88            let e: usize = sc.read();
89            let mut graph = vec![vec![]; v];
90            for _ in 0..e {
91                let s: usize = sc.read();
92                let t: usize = sc.read();
93                graph[s].push(t);
94            }
95
96            let cmp = strongly_connected_components::decompose(&graph);
97            let q: usize = sc.read();
98            for _ in 0..q {
99                let u: usize = sc.read();
100                let v: usize = sc.read();
101
102                if cmp[u] == cmp[v] {
103                    sc.write("1\n");
104                } else {
105                    sc.write("0\n");
106                }
107            }
108        });
109    }
110}
competitive_programming_rs/graph/strongly_connected_components.rs

competitive_programming_rs/graph/
strongly_connected_components.rs
