competitive/tree/
tree_order.rs

1use crate::graph::SparseGraph;
2
3#[codesnip::entry("tree_order", include("SparseGraph"))]
4impl<D> SparseGraph<D> {
5    /// (order, parents)
6    pub fn tree_order(&self, root: usize) -> (Vec<usize>, Vec<usize>) {
7        let n = self.vertices_size();
8        let mut order = Vec::with_capacity(n);
9        let mut parents = vec![!0usize; n];
10        let mut stack = Vec::with_capacity(n);
11        stack.push(root);
12        while let Some(u) = stack.pop() {
13            order.push(u);
14            for a in self.adjacencies(u).rev() {
15                if a.to != parents[u] {
16                    parents[a.to] = u;
17                    stack.push(a.to);
18                }
19            }
20        }
21        (order, parents)
22    }
23}