class NgLib:: LCA

• NgLib::LCA
• Reference
• Object

Overview

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

Defined in:

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