competitive_programming_rs/graph/
bridge_detection.rs

1pub struct BridgeDetector {
2    articulations: Vec<usize>,
3    bridges: Vec<(usize, usize)>,
4    visit: Vec<bool>,
5    order: Vec<usize>,
6    low_link: Vec<usize>,
7    k: usize,
8}
9
10impl BridgeDetector {
11    pub fn new(graph: &[Vec<usize>]) -> Self {
12        let n = graph.len();
13        let mut d = BridgeDetector {
14            articulations: vec![],
15            bridges: vec![],
16            visit: vec![false; n],
17            order: vec![0; n],
18            low_link: vec![0; n],
19            k: 0,
20        };
21        d.run(graph);
22        d
23    }
24
25    fn run(&mut self, graph: &[Vec<usize>]) {
26        let n = graph.len();
27        for i in 0..n {
28            if !self.visit[i] {
29                self.dfs(i, 0, graph, i);
30            }
31        }
32    }
33
34    fn dfs(&mut self, v: usize, previous: usize, graph: &[Vec<usize>], root: usize) {
35        self.visit[v] = true;
36        self.order[v] = self.k;
37        self.k += 1;
38        self.low_link[v] = self.order[v];
39
40        let mut is_articulation = false;
41        let mut dimension = 0;
42        for &next in graph[v].iter() {
43            if !self.visit[next] {
44                // The edge (v->next) is not a backedge.
45                dimension += 1;
46                self.dfs(next, v, graph, root);
47                self.low_link[v] = std::cmp::min(self.low_link[v], self.low_link[next]);
48                if v != root && self.order[v] <= self.low_link[next] {
49                    is_articulation = true;
50                }
51                if self.order[v] < self.low_link[next] {
52                    let min = std::cmp::min(v, next);
53                    let max = std::cmp::max(v, next);
54                    self.bridges.push((min, max));
55                }
56            } else if v == root || next != previous {
57                // The edge (v->next) is a back-edge.
58                self.low_link[v] = std::cmp::min(self.low_link[v], self.order[next]);
59            }
60        }
61
62        if v == root && dimension > 1 {
63            is_articulation = true;
64        }
65        if is_articulation {
66            self.articulations.push(v);
67        }
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74    use crate::utils::test_helper::Tester;
75
76    #[test]
77    fn solve_grl_3_a() {
78        let tester = Tester::new("./assets/GRL_3_A/in/", "./assets/GRL_3_A/out/");
79
80        tester.test_solution(|sc| {
81            let n: usize = sc.read();
82            let m: usize = sc.read();
83
84            let mut graph = vec![vec![]; n];
85            for _ in 0..m {
86                let u: usize = sc.read();
87                let v: usize = sc.read();
88                graph[u].push(v);
89                graph[v].push(u);
90            }
91
92            let mut low_link_link = BridgeDetector::new(&graph);
93            low_link_link.articulations.sort();
94
95            for v in low_link_link.articulations.into_iter() {
96                sc.write(format!("{}\n", v));
97            }
98        });
99    }
100
101    #[test]
102    fn solve_grl_3_b() {
103        let tester = Tester::new("./assets/GRL_3_B/in/", "./assets/GRL_3_B/out/");
104        tester.test_solution(|sc| {
105            let n: usize = sc.read();
106            let m: usize = sc.read();
107            let mut graph = vec![vec![]; n];
108            for _ in 0..m {
109                let u: usize = sc.read();
110                let v: usize = sc.read();
111                graph[u].push(v);
112                graph[v].push(u);
113            }
114
115            let mut low_link_link = BridgeDetector::new(&graph);
116            low_link_link.bridges.sort();
117
118            for (a, b) in low_link_link.bridges.into_iter() {
119                sc.write(format!("{} {}\n", a, b));
120            }
121        });
122    }
123}
competitive_programming_rs/graph/bridge_detection.rs

competitive_programming_rs/graph/
bridge_detection.rs
