Function auxiliary_tree::auxiliary_tree

source · 
pub fn auxiliary_tree(
    nodes: &[usize],
    inv_ord: &[usize],
    lca: &LowestCommonAncestor
) -> (usize, HashMap<usize, Vec<usize>>)
Expand description

auxiliary tree です。

計算量

hash map のコストは無視する。

グラフの頂点数を n, nodes.len() を k として、O(klogn + klogk)

引数

  • nodes： {0, 1, …, n - 1} の部分集合
  • inv_ord: pre-order (行きがけ順) の列の添字と値を反対にしたもの
    • 頂点 i は行きがけ順で inv_ord[i] 番目に現われる
  • lca: 2頂点の LCA を得る .get(u, v) を実装した構造体

返り値

(root, g)

  • g.contains_key(&i): 頂点 i が圧縮後の木に含まれて、子のリストが g[&i] である
  • !g.contains_key(&i): 頂点 i が圧縮後の木に含まれない