competitive/graph/
low_link.rs

1use super::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, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, p: 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.adjacencies(u) {
33            if self.ord[a.to] == usize::MAX {
34                cnt += 1;
35                self.dfs(a.to, u, now_ord);
36                self.low[u] = self.low[u].min(self.low[a.to]);
37                is_articulation |= p < self.graph.vertices_size() && self.ord[u] <= self.low[a.to];
38                if self.ord[u] < self.low[a.to] {
39                    self.bridge.push((u.min(a.to), u.max(a.to)));
40                }
41            } else if a.to != p {
42                self.low[u] = self.low[u].min(self.ord[a.to]);
43            }
44        }
45        is_articulation |= p == self.graph.vertices_size() && cnt > 1;
46        if is_articulation {
47            self.articulation.push(u);
48        }
49    }
50}
competitive/graph/low_link.rs

competitive/graph/
low_link.rs
