cp_library_rs/graph/
namori.rs

1//! なもりグラフの分解
2
3use std::collections::VecDeque;
4
5pub type Graph = Vec<Vec<usize>>;
6
7/// # なもりグラフ
8/// - なもりグラフ（木に辺を1本加えたグラフ）を分解する
9#[derive(Debug)]
10pub struct Namori {
11    pub N: usize,
12    pub graph: Graph,
13    pub forest: Graph,
14    pub on_cycle: Vec<bool>,
15}
16
17impl Namori {
18    /// 頂点数`N`のグラフを作成する
19    pub fn new(N: usize) -> Self {
20        Self {
21            N,
22            graph: vec![vec![]; N],
23            forest: vec![vec![]; N],
24            on_cycle: vec![true; N],
25        }
26    }
27
28    /// 頂点`u`,`v`に辺を張る
29    pub fn add_edge(&mut self, u: usize, v: usize) {
30        self.graph[u].push(v);
31        self.graph[v].push(u);
32    }
33
34    /// なもりグラフを分解し、
35    /// - サイクルを取り除いた森
36    /// - サイクル上の頂点
37    ///
38    /// を求める
39    pub fn decompose(&mut self) {
40        // 葉を調べる
41        let mut degree = vec![0; self.N];
42        let mut leafs = VecDeque::new();
43        let mut visited = vec![false; self.N];
44        for i in 0..self.N {
45            degree[i] = self.graph[i].len(); // 次数を調べる
46                                             // 次数が1の頂点を格納
47            if degree[i] == 1 {
48                leafs.push_back(i);
49                visited[i] = true;
50            }
51        }
52        // 葉を辿って木に分解
53        while let Some(u) = leafs.pop_front() {
54            self.on_cycle[u] = false;
55            for &v in &self.graph[u] {
56                if visited[v] {
57                    continue;
58                }
59                degree[v] -= 1;
60                // 森に追加
61                self.forest[u].push(v);
62                self.forest[v].push(u);
63                if degree[v] <= 1 {
64                    leafs.push_back(v);
65                    visited[v] = true;
66                }
67            }
68        }
69    }
70}
cp_library_rs/graph/namori.rs

cp_library_rs/graph/
namori.rs
