Types
Functional_Graph = ref object tree*: HeavyLightDecomposition cycle_number*: seq[int] cycle_idx*: seq[int] roots*: seq[int] cycle*: seq[seq[int]] depth_tin: seq[seq[int]] cycle_depth: seq[seq[seq[int]]] component_size: seq[int]
- Source Edit
Procs
proc canmove_size(functional_graph: Functional_Graph; x: int): int {....raises: [], tags: [].}
- xから到達することのできる頂点数(xも含む) Source Edit
proc compressed_forest(functional_graph: Functional_Graph): ( UnWeightedUnDirectedGraph, seq[int], seq[int]) {....raises: [], tags: [].}
- 各サイクルを1頂点に圧縮した根付き森を返す。O(N) 返り値は (森, 元の頂点から圧縮後の頂点への対応, 各木の根) 。 根は functional_graph.cycle と同じ順番で並ぶ。 Source Edit
proc count_kth(functional_graph: Functional_Graph; x, k: int): int {....raises: [], tags: [].}
- 各頂点にコマを1つずつ置いてk回移動したとき、頂点xにあるコマの数 O(log N) Source Edit
proc cyclesize(functional_graph: Functional_Graph; x: int): int {....raises: [], tags: [].}
- xから到達することができるサイクルのサイズ Source Edit
proc depth(functional_graph: Functional_Graph; x: int): int {....raises: [], tags: [].}
- 何回の移動でcycleに入るか Source Edit
proc dist(functional_graph: Functional_Graph; u, v: int): int {....raises: [], tags: [].}
- uからvへ最短何回の移動で到達が可能か ただし、到達できないときは-1を返す。 Source Edit
proc get_cycle(functional_graph: Functional_Graph; x: int): seq[int] {. ...raises: [], tags: [].}
- xから到達できるサイクルを返す Source Edit
proc incycle(namori: Functional_Graph; x: int): bool {....raises: [], tags: [].}
- Source Edit
proc initFunctionalGraph(graph: UnWeightedDirectedGraph): Functional_Graph {. ...raises: [], tags: [].}
- Source Edit
proc initFunctionalGraph(v: openArray[int]): Functional_Graph {....raises: [], tags: [].}
- Source Edit
proc movekth(functional_graph: Functional_Graph; x, cnt: int): int {....raises: [], tags: [].}
- Source Edit
proc reachable_to_size(functional_graph: Functional_Graph; x: int): int {. ...raises: [], tags: [].}
- xに到達することのできる頂点数(xも含む) Source Edit
proc root(functional_graph: Functional_Graph; x: int): int {....raises: [], tags: [].}
- xから進んでいったときに、初めてサイクルに入ったときの頂点を返す Source Edit
proc walk(functional_graph: Functional_Graph; x, k: int): seq[int] {....raises: [], tags: [].}
- xを始点としてk回移動するまでに訪れる頂点を、始点を含む長さk+1の配列で返す。O(k) Source Edit