competitive_library/graph/
euler_tour.rs

1#[derive(Debug)]
2pub enum Vertex {
3    In(usize),
4    Out(usize),
5}
6impl Vertex {
7    pub fn get_value(&self) -> usize {
8        match self {
9            Vertex::In(value) => *value,
10            Vertex::Out(value) => *value,
11        }
12    }
13}
14use std::collections::VecDeque;
15
16pub fn euler_tour(e: &[Vec<usize>], root: usize) -> (Vec<usize>, Vec<usize>, Vec<usize>) {
17    let mut stack = VecDeque::new();
18    stack.push_back(Vertex::In(root));
19    let mut tour = vec![];
20    let mut first_look = vec![None; e.len()];
21    let mut depth = 0;
22    let mut depths = vec![0; e.len()];
23    while let Some(vertex) = stack.pop_back() {
24        if let Vertex::In(v) = vertex {
25            for &to in e[v].iter() {
26                if first_look[to].is_some() {
27                    continue;
28                }
29                stack.push_back(Vertex::Out(v));
30                stack.push_back(Vertex::In(to));
31            }
32            first_look[v] = Some(tour.len());
33            depths[v] = depth;
34            depth += 1;
35        } else {
36            depth -= 1;
37        }
38        tour.push(vertex.get_value());
39    }
40
41    (
42        tour,
43        first_look.iter().map(|x| x.unwrap()).collect(),
44        depths,
45    )
46}
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_eiler_tour() {
54        let e = vec![vec![5, 1], vec![4, 2], vec![3], vec![], vec![], vec![]];
55        let (ans, _, _) = euler_tour(&e, 0);
56        assert_eq!(&ans, &[0, 1, 2, 3, 2, 1, 4, 1, 0, 5, 0]);
57    }
58}
competitive_library/graph/euler_tour.rs

competitive_library/graph/
euler_tour.rs
