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
63
64
65
66
67
68
69
70
71
72

use crate::graph::graph::Graph;

pub struct EulerTour {
    graph: Graph,
    l: Vec<usize>,
    r: Vec<usize>,
    t: usize,
}

impl EulerTour {
    const INF: usize = 100_000_000_000_000_000;

    pub fn new(n: usize, graph: Graph) -> Self {
        let l = vec![Self::INF; n];
        let r = vec![Self::INF; n];
        Self { graph, l, r, t: 1 }
    }

    /// Euler tour entrypoint that returns two vectors `(&l, &r)`.
    /// Note that timestamp starts from `1`.
    ///
    /// - `l`: vector indicates the timestamp that visits a node `u` at the first time.
    /// - `r`: vector indicates the timestamp that visits a node `u` at the last time.
    pub fn traverse(&mut self, root: usize) -> (&[usize], &[usize]) {
        self._dfs(root, None);

        for i in 0..self.l.len() {
            if self.r[i] == Self::INF {
                self.r[i] = self.l[i];
            }
        }

        (&self.l, &self.r)
    }

    fn _dfs(&mut self, u: usize, p: Option<usize>) {
        self.l[u] = self.t;
        self.t += 1;

        for i in 0..self.graph.graph[u].len() {
            let (v, _) = self.graph.graph[u][i];
            if p != Some(v) {
                self._dfs(v, Some(u));
                self.r[u] = self.t;
                self.t += 1;
            }
        }
    }
}

#[cfg(test)]
mod test_euler_tour {
    use crate::graph::euler_tour::EulerTour;
    use crate::graph::graph::Graph;

    #[test]
    fn it_works() {
        let mut graph = Graph::new(7, false);
        graph.connect_unweighted(0, 1);
        graph.connect_unweighted(1, 2);
        graph.connect_unweighted(1, 3);
        graph.connect_unweighted(3, 4);
        graph.connect_unweighted(0, 5);
        graph.connect_unweighted(5, 6);

        let mut euler_tour = EulerTour::new(7, graph);
        let (l, r) = euler_tour.traverse(0);

        assert_eq!(l, &vec![1, 2, 3, 5, 6, 10, 11]);
        assert_eq!(r, &vec![13, 8, 3, 7, 6, 12, 11]);
    }
}