haar_lib/graph/
two_edge.rs

1//! 二重辺連結成分分解
2
3pub use crate::graph::lowlink::*;
4
5/// 二重辺連結成分分解
6pub fn two_edge_connected_components(ll: &Lowlink) -> Vec<Vec<usize>> {
7    let mut ret = vec![];
8
9    for i in 0..ll.size {
10        if ll.par[i].is_none() {
11            let index = ret.len();
12            ret.push(vec![]);
13            rec(ll, i, index, &mut ret);
14        }
15    }
16
17    ret
18}
19
20fn rec(ll: &Lowlink, cur: usize, index: usize, ret: &mut Vec<Vec<usize>>) {
21    ret[index].push(cur);
22
23    for &to in &ll.ch[cur] {
24        if ll.ord[cur] < ll.low[to] {
25            let index = ret.len();
26            ret.push(vec![]);
27            rec(ll, to, index, ret);
28        } else {
29            rec(ll, to, index, ret);
30        }
31    }
32}
33
34#[cfg(test)]
35mod tests {
36    use super::*;
37    use crate::{btreeset, graph::*};
38    use std::{collections::BTreeSet, iter::FromIterator};
39
40    #[test]
41    fn test() {
42        let mut g = Graph::<Undirected, _>::new(4);
43        g.extend(
44            vec![(0, 2), (0, 1), (3, 0), (2, 1), (2, 3)]
45                .into_iter()
46                .map(|(u, v)| Edge::new(u, v, (), ())),
47        );
48
49        let ans = two_edge_connected_components(&Lowlink::new(&g));
50        let ans = BTreeSet::from_iter(ans.into_iter().map(BTreeSet::from_iter));
51        assert_eq!(ans, btreeset! {btreeset!{0, 1, 2, 3}});
52
53        let mut g = Graph::<Undirected, _>::new(13);
54        g.extend(
55            vec![
56                (4, 5),
57                (8, 7),
58                (12, 3),
59                (3, 10),
60                (1, 5),
61                (10, 2),
62                (0, 0),
63                (11, 4),
64                (2, 12),
65                (9, 1),
66                (9, 0),
67                (7, 8),
68                (7, 6),
69                (9, 1),
70                (8, 2),
71                (12, 10),
72                (11, 0),
73                (8, 6),
74                (3, 2),
75                (5, 9),
76                (4, 11),
77            ]
78            .into_iter()
79            .map(|(u, v)| Edge::new(u, v, (), ())),
80        );
81
82        let ans = two_edge_connected_components(&Lowlink::new(&g));
83        let ans = BTreeSet::from_iter(ans.into_iter().map(BTreeSet::from_iter));
84
85        assert_eq!(
86            ans,
87            btreeset! {
88                btreeset!{0, 1, 4, 5, 9, 11},
89                btreeset!{2, 3, 10, 12},
90                btreeset!{6, 7, 8}
91            }
92        );
93    }
94}
haar_lib/graph/two_edge.rs

haar_lib/graph/
two_edge.rs
