functional_graph

struct functional_graph;

概要

各頂点の出次数が1のfunctional graph

名前	説明	計算量
`(constructor)`	(1) 空のfunctional graphを構築する (2) 各頂点の遷移先toから構築する	(1) $O(1)$ (2) $O(V)$

名前	説明	計算量
`size`	頂点数を返す	$O(1)$
`jump`	頂点vからstep回遷移した頂点を返す	$O(\log V)$
`jump_all`	全頂点からstep回遷移した頂点をまとめて返す	$O(V)$
`dist`	uからvへ到達するまでの遷移回数を返し、到達不能なら-1を返す	$O(1)$
`cycle_length`	vが流入するサイクルの長さを返す	$O(1)$
`get_cycles`	すべてのサイクルを頂点列として返す	$O(V)$
`root`	vが流入するサイクルの代表頂点を返す	$O(1)$
`depth`	反転木上の深さを返す	$O(1)$
`in_cycle`	vがサイクル上にあるか返す	$O(1)$
`lca`	同じ反転木に属するuとvのLCAを返す	$O(\log V)$

// (1)
functional_graph() = default;

// (2)
functional_graph(const std::vector<int> &_to);

(1) 空のfunctional graphを構築する

(2) 各頂点の遷移先toから構築する