competitive/graph/
low_link.rs

1use super::{Graph, UndirectedSparseGraph};
2
3pub struct LowLink<'a> {
4    graph: &'a UndirectedSparseGraph,
5    pub low: Vec<usize>,
6    pub ord: Vec<usize>,
7    pub articulation: Vec<usize>,
8    pub bridge: Vec<(usize, usize)>,
9}
10impl<'a> LowLink<'a> {
11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, !0, &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, parent_eid: usize, now_ord: &mut usize) {
27        self.low[u] = *now_ord;
28        self.ord[u] = *now_ord;
29        *now_ord += 1;
30        let mut is_articulation = false;
31        let mut cnt = 0;
32        for a in self.graph.neighbors(u) {
33            if a.label == parent_eid {
34                continue;
35            }
36            if self.ord[a.to] == usize::MAX {
37                cnt += 1;
38                self.dfs(a.to, a.label, now_ord);
39                self.low[u] = self.low[u].min(self.low[a.to]);
40                is_articulation |= parent_eid != !0 && self.ord[u] <= self.low[a.to];
41                if self.ord[u] < self.low[a.to] {
42                    self.bridge.push((u.min(a.to), u.max(a.to)));
43                }
44            } else {
45                self.low[u] = self.low[u].min(self.ord[a.to]);
46            }
47        }
48        is_articulation |= parent_eid == !0 && cnt > 1;
49        if is_articulation {
50            self.articulation.push(u);
51        }
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58    use crate::{rand, tools::Xorshift};
59
60    fn components(
61        n: usize,
62        edges: &[(usize, usize)],
63        removed_vertex: usize,
64        removed_eid: usize,
65    ) -> usize {
66        let mut visited = vec![false; n];
67        if removed_vertex < n {
68            visited[removed_vertex] = true;
69        }
70        let mut count = 0;
71        for root in 0..n {
72            if visited[root] {
73                continue;
74            }
75            count += 1;
76            visited[root] = true;
77            let mut stack = vec![root];
78            while let Some(u) = stack.pop() {
79                for (eid, &(from, to)) in edges.iter().enumerate() {
80                    if eid == removed_eid {
81                        continue;
82                    }
83                    let v = if from == u {
84                        to
85                    } else if to == u {
86                        from
87                    } else {
88                        continue;
89                    };
90                    if !visited[v] {
91                        visited[v] = true;
92                        stack.push(v);
93                    }
94                }
95            }
96        }
97        count
98    }
99
100    #[test]
101    fn test_low_link() {
102        const Q: usize = 1_000;
103        const N: usize = 8;
104        const M: usize = 20;
105        let mut rng = Xorshift::default();
106        for _ in 0..Q {
107            rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
108            let component_count = components(n, &edges, !0, !0);
109            let expected_articulation: Vec<_> = (0..n)
110                .filter(|&vertex| components(n, &edges, vertex, !0) > component_count)
111                .collect();
112            let mut expected_bridges: Vec<_> = edges
113                .iter()
114                .enumerate()
115                .filter(|&(eid, _)| components(n, &edges, !0, eid) > component_count)
116                .map(|(_, &(u, v))| (u.min(v), u.max(v)))
117                .collect();
118            expected_bridges.sort_unstable();
119
120            let graph = UndirectedSparseGraph::from_edges(n, edges);
121            let mut low_link = LowLink::new(&graph);
122            low_link.articulation.sort_unstable();
123            low_link.bridge.sort_unstable();
124
125            assert_eq!(low_link.articulation, expected_articulation);
126            assert_eq!(low_link.bridge, expected_bridges);
127        }
128    }
129}
competitive/graph/low_link.rs

competitive/graph/
low_link.rs
