1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

//! オイラーツアー

use crate::utils::consts::INF;

/// EulerTour
#[derive(Debug)]
pub struct EulerTour {
    pub G: Vec<Vec<usize>>,
    pub in_: Vec<usize>,
    pub out: Vec<usize>,
    pub depth: Vec<usize>,
}

impl EulerTour {
    /// 木を初期化する
    pub fn new(N: usize) -> Self {
        Self {
            G: vec![vec![]; N],
            in_: vec![INF; N],
            out: vec![INF; N],
            depth: vec![INF; N],
        }
    }

    /// 辺 `(u,v)` を追加する
    pub fn add_edge(&mut self, u: usize, v: usize) {
        self.G[u].push(v);
        self.G[v].push(u);
    }

    /// 順序付けを行う
    pub fn build(&mut self, root: usize) {
        self.dfs(INF, root, &mut 0, &mut 0);
    }

    /// 行きがけ順，帰りがけ順で順序付け
    fn dfs(&mut self, p: usize, u: usize, id: &mut usize, depth: &mut usize) {
        self.in_[u] = *id;
        self.depth[u] = *depth;

        *depth += 1;

        for i in 0..self.G[u].len() {
            let v = self.G[u][i];
            if v == p {
                continue;
            }
            *id += 1;
            self.dfs(u, v, id, depth);
        }

        *depth -= 1;
        *id += 1;

        self.out[u] = *id;
    }

    /// 頂点`v`の (行きがけ順,帰りがけ順) のタプルを返す
    pub fn get_id(&self, v: usize) -> (usize, usize) {
        (self.in_[v], self.out[v])
    }
}