cp_library_rs/graph/
euler_tour.rs

1//! オイラーツアー
2
3use crate::utils::consts::Infinity;
4
5/// EulerTour
6#[derive(Debug)]
7pub struct EulerTour {
8    pub G: Vec<Vec<usize>>,
9    pub in_: Vec<usize>,
10    pub out: Vec<usize>,
11    pub depth: Vec<usize>,
12}
13
14impl EulerTour {
15    /// 木を初期化する
16    pub fn new(N: usize) -> Self {
17        Self {
18            G: vec![vec![]; N],
19            in_: vec![usize::infinity(); N],
20            out: vec![usize::infinity(); N],
21            depth: vec![usize::infinity(); N],
22        }
23    }
24
25    /// 辺 `(u,v)` を追加する
26    pub fn add_edge(&mut self, u: usize, v: usize) {
27        self.G[u].push(v);
28        self.G[v].push(u);
29    }
30
31    /// 順序付けを行う
32    pub fn build(&mut self, root: usize) {
33        self.dfs(usize::infinity(), root, &mut 0, &mut 0);
34    }
35
36    /// 行きがけ順，帰りがけ順で順序付け
37    fn dfs(&mut self, p: usize, u: usize, id: &mut usize, depth: &mut usize) {
38        self.in_[u] = *id;
39        self.depth[u] = *depth;
40
41        *depth += 1;
42
43        for i in 0..self.G[u].len() {
44            let v = self.G[u][i];
45            if v == p {
46                continue;
47            }
48            *id += 1;
49            self.dfs(u, v, id, depth);
50        }
51
52        *depth -= 1;
53        *id += 1;
54
55        self.out[u] = *id;
56    }
57
58    /// 頂点`v`の (行きがけ順,帰りがけ順) のタプルを返す
59    pub fn get_id(&self, v: usize) -> (usize, usize) {
60        (self.in_[v], self.out[v])
61    }
62}
cp_library_rs/graph/euler_tour.rs

cp_library_rs/graph/
euler_tour.rs
