1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

pub struct BridgeDetector {
    articulations: Vec<usize>,
    bridges: Vec<(usize, usize)>,
    visit: Vec<bool>,
    order: Vec<usize>,
    low_link: Vec<usize>,
    k: usize,
}

impl BridgeDetector {
    pub fn new(graph: &[Vec<usize>]) -> Self {
        let n = graph.len();
        let mut d = BridgeDetector {
            articulations: vec![],
            bridges: vec![],
            visit: vec![false; n],
            order: vec![0; n],
            low_link: vec![0; n],
            k: 0,
        };
        d.run(graph);
        d
    }

    fn run(&mut self, graph: &[Vec<usize>]) {
        let n = graph.len();
        for i in 0..n {
            if !self.visit[i] {
                self.dfs(i, 0, graph, i);
            }
        }
    }

    fn dfs(&mut self, v: usize, previous: usize, graph: &[Vec<usize>], root: usize) {
        self.visit[v] = true;
        self.order[v] = self.k;
        self.k += 1;
        self.low_link[v] = self.order[v];

        let mut is_articulation = false;
        let mut dimension = 0;
        for &next in graph[v].iter() {
            if !self.visit[next] {
                // The edge (v->next) is not a backedge.
                dimension += 1;
                self.dfs(next, v, graph, root);
                self.low_link[v] = std::cmp::min(self.low_link[v], self.low_link[next]);
                if v != root && self.order[v] <= self.low_link[next] {
                    is_articulation = true;
                }
                if self.order[v] < self.low_link[next] {
                    let min = std::cmp::min(v, next);
                    let max = std::cmp::max(v, next);
                    self.bridges.push((min, max));
                }
            } else if v == root || next != previous {
                // The edge (v->next) is a back-edge.
                self.low_link[v] = std::cmp::min(self.low_link[v], self.order[next]);
            }
        }

        if v == root && dimension > 1 {
            is_articulation = true;
        }
        if is_articulation {
            self.articulations.push(v);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::utils::test_helper::Tester;

    #[test]
    fn solve_grl_3_a() {
        let tester = Tester::new("./assets/GRL_3_A/in/", "./assets/GRL_3_A/out/");

        tester.test_solution(|sc| {
            let n: usize = sc.read();
            let m: usize = sc.read();

            let mut graph = vec![vec![]; n];
            for _ in 0..m {
                let u: usize = sc.read();
                let v: usize = sc.read();
                graph[u].push(v);
                graph[v].push(u);
            }

            let mut low_link_link = BridgeDetector::new(&graph);
            low_link_link.articulations.sort();

            for v in low_link_link.articulations.into_iter() {
                sc.write(format!("{}\n", v));
            }
        });
    }

    #[test]
    fn solve_grl_3_b() {
        let tester = Tester::new("./assets/GRL_3_B/in/", "./assets/GRL_3_B/out/");
        tester.test_solution(|sc| {
            let n: usize = sc.read();
            let m: usize = sc.read();
            let mut graph = vec![vec![]; n];
            for _ in 0..m {
                let u: usize = sc.read();
                let v: usize = sc.read();
                graph[u].push(v);
                graph[v].push(u);
            }

            let mut low_link_link = BridgeDetector::new(&graph);
            low_link_link.bridges.sort();

            for (a, b) in low_link_link.bridges.into_iter() {
                sc.write(format!("{} {}\n", a, b));
            }
        });
    }
}