competitive-programming-rs 22.0.0

Competitive Programming Library in Rust
Documentation 
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));
            }
        });
    }
}