haar_lib/graph/
articulation_points.rs

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

haar_lib/graph/
articulation_points.rs
