haar_lib/graph/
pseudo_tree.rs

1//! 閉路をただ一つだけもつN辺N頂点の連結無向グラフ。
2//!
3//! # References
4//! - <https://en.wikipedia.org/wiki/Pseudoforest>
5//!
6//! # Problems
7//! - <https://atcoder.jp/contests/abc266/tasks/abc266_f>
8
9use std::collections::VecDeque;
10
11/// [`PseudoTree`]を構築するための構造体。
12pub struct PseudoTreeBuilder {
13    edge_num: usize,
14    g: Vec<Vec<usize>>,
15}
16
17/// 閉路をただ一つだけもつN辺N頂点の連結無向グラフ。
18pub struct PseudoTree {
19    root: Vec<usize>,
20    kind: Vec<Kind>,
21}
22
23/// [`PseudoTree`]の頂点の種類
24#[derive(Clone, Copy, PartialEq, Debug)]
25pub enum Kind {
26    /// 閉路を構成する頂点。
27    Loop,
28    /// 閉路以外の頂点。
29    Other,
30}
31
32impl Kind {
33    /// `Loop`ならば`true`を返す。
34    pub fn is_loop(self) -> bool {
35        matches!(self, Self::Loop)
36    }
37}
38
39impl PseudoTreeBuilder {
40    /// 頂点数`n`の空のグラフを用意する。
41    pub fn new(n: usize) -> Self {
42        Self {
43            g: vec![vec![]; n],
44            edge_num: 0,
45        }
46    }
47
48    /// `u, v`間に無向辺を張る。
49    pub fn add(&mut self, u: usize, v: usize) {
50        self.g[u].push(v);
51        self.g[v].push(u);
52        self.edge_num += 1;
53    }
54
55    /// [`PseudoTree`]を構築する。
56    pub fn build(self) -> PseudoTree {
57        assert_eq!(self.edge_num, self.g.len());
58        let n = self.g.len();
59        let mut indeg = vec![0; n];
60        let mut visit = vec![false; n];
61        let mut kind = vec![Kind::Loop; n];
62
63        for &to in self.g.iter().flatten() {
64            indeg[to] += 1;
65        }
66
67        let mut queue: VecDeque<_> = indeg
68            .iter()
69            .enumerate()
70            .filter_map(|(i, &deg)| (deg == 1).then_some(i))
71            .collect();
72
73        while let Some(cur) = queue.pop_front() {
74            kind[cur] = Kind::Other;
75            if visit[cur] {
76                continue;
77            }
78            visit[cur] = true;
79
80            for &to in &self.g[cur] {
81                if !visit[to] {
82                    indeg[to] -= 1;
83
84                    if indeg[to] == 1 {
85                        queue.push_back(to);
86                    }
87                }
88            }
89        }
90
91        let mut root = vec![0; n];
92
93        for i in 0..n {
94            if kind[i].is_loop() {
95                root[i] = i;
96                for &to in &self.g[i] {
97                    if !kind[to].is_loop() {
98                        self.__dfs(to, i, &mut root);
99                    }
100                }
101            }
102        }
103
104        PseudoTree { root, kind }
105    }
106
107    fn __dfs(&self, cur: usize, par: usize, root: &mut [usize]) {
108        root[cur] = root[par];
109
110        for &to in &self.g[cur] {
111            if to != par {
112                self.__dfs(to, cur, root);
113            }
114        }
115    }
116}
117
118impl PseudoTree {
119    /// 頂点`i`から辺を辿って最初に到達する閉路頂点を返す。
120    pub fn root_of(&self, i: usize) -> usize {
121        self.root[i]
122    }
123
124    /// 頂点`i`の種類を返す。
125    pub fn kind_of(&self, i: usize) -> Kind {
126        self.kind[i]
127    }
128}
haar_lib/graph/pseudo_tree.rs

haar_lib/graph/
pseudo_tree.rs
