class NgLib::LCA

• NgLib::LCA
• Reference
• Object

Overview

最近共通祖先を求めるライブラリです。

Defined in:

nglib/graph/lca.cr

Constructors

• .new(graph : Graph, root = 0_i64)

  木構造グラフ graph に対して、root を根とする LCA を構築します。

Instance Method Summary

• #ancestor(u : Int, v : Int) : Int64

  頂点 $u$ と 頂点 $v$ の最近共通祖先を返します。

• #dist : Array(Int64)
• #distance_between(u : Int, v : Int) : Int64

  頂点 $u$ と頂点 $v$ の距離を返します。

• #on_path?(u : Int, v : Int, a : Int) : Bool

  頂点 $u$ から頂点 $v$ までのパスに頂点 $a$ が含まれているか返します。

• #parent : Array(Array(Int64))

Constructor Detail

Instance Method Detail