competitive/tree/
tree_order.rs

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

competitive/tree/
tree_order.rs
