haar_lib/graph/
bridges.rs

1//! 橋の列挙
2
3pub use crate::graph::lowlink::*;
4
5/// 橋の列挙
6///
7/// **Time complexity** $O(V + E)$
8pub fn bridges(ll: &Lowlink) -> Vec<(usize, usize)> {
9    let Lowlink { ord, low, ch, .. } = ll;
10
11    ch.iter()
12        .enumerate()
13        .flat_map(|(i, es)| {
14            es.iter()
15                .filter_map(|&j| (ord[i] < low[j]).then_some((i, j)))
16                .collect::<Vec<_>>()
17        })
18        .collect()
19}
20
21#[cfg(test)]
22mod tests {
23    use super::*;
24    use crate::graph::*;
25
26    #[test]
27    fn test() {
28        // https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_3_B
29        let mut g = Graph::<Undirected, _>::new(4);
30        g.extend(
31            vec![(0, 1), (0, 2), (1, 2), (2, 3)]
32                .into_iter()
33                .map(|(u, v)| Edge::new(u, v, (), ())),
34        );
35        let mut ans = bridges(&Lowlink::new(&g));
36        ans.sort();
37        assert_eq!(ans, [(2, 3)]);
38
39        let mut g = Graph::<Undirected, _>::new(5);
40        g.extend(
41            vec![(0, 1), (1, 2), (2, 3), (3, 4)]
42                .into_iter()
43                .map(|(u, v)| Edge::new(u, v, (), ())),
44        );
45        let mut ans = bridges(&Lowlink::new(&g));
46        ans.sort();
47        assert_eq!(ans, [(0, 1), (1, 2), (2, 3), (3, 4)]);
48    }
49}
haar_lib/graph/bridges.rs

haar_lib/graph/
bridges.rs
