class

NgLib::PotentializedDisjointSet(Abel)

Inherits Reference < Object

重み付き DSU (Union-Find) などと呼ばれるデータ構造です。

Abel 群を載せることができます。すなわち、次のメソッドが実装されているオブジェクトが載ります。

#zero
+
-

Constructors

new(size : Int)

n 頂点 0 辺の無向グラフを作ります。

n = int
ut = PotentializedDisjointSet(Abel).new(n)

Source

new

0 頂点 0 辺の無向グラフを作ります。

ut = PotentializedDisjointSet(Abel).new

Source

Instance methods

diff(low : Int, high : Int) : Abel

w[high] - w[low] を返します。

low と high が同じ連結成分に属していない場合 Abel.zero を返します。

ut = PotentializedDisjointSet(Abel).new(size: 10)
ut.unite(2, 1, 1)
ut.unite(2, 3, 5)
ut.unite(3, 4, 2)
ut.diff(1, 2) # => -1
ut.diff(2, 1) # => 1
ut.diff(2, 3) # => 5
ut.diff(2, 4) # => 7
ut.diff(0, 9) # => Abel.zero

Source

diff?(low : Int, high : Int) : Abel | Nil

w[high] - w[low] を返します。

low と high が同じ連結成分に属していない場合 nil を返します。

ut = PotentializedDisjointSet(Abel).new(size: 10)
ut.unite(2, 1, 1)
ut.unite(2, 3, 5)
ut.unite(3, 4, 2)
ut.diff(1, 2) # => -1
ut.diff(2, 1) # => 1
ut.diff(2, 3) # => 5
ut.diff(2, 4) # => 7
ut.diff(0, 9) # => nil

Source

equiv?(a : Int, b : Int) : Bool

頂点 a と頂点 b が同じ連結成分に属しているなら true を返します。

n = int
ut = PotentializedDisjointSet(Abel).new(n)
ut.equiv?(u, v) # => true

Source

groups

グラフを連結成分に分け、その情報を返します。

返り値は「「一つの連結成分の頂点番号のリスト」のリスト」です。（内側外側限らず）Array 内でどの順番で頂点が格納されているかは未定義です。

Source

leader(a : Int) : Int64

頂点 a の属する連結成分のリーダーを返します。

n = int
ut = PotentializedDisjointSet(Abel).new(n)
ut.unite(2, 3, 0)
ut.leader(0) # => 0
ut.leader(3) # => 2  (3 の可能性もある)

Source

size(a : Int) : Int64

頂点 a が属する連結成分の大きさを返します。

Source

unite(low : Int, high : Int, diff : Abel) : Int64

w[high] - w[low] = diff となるように、頂点 low と頂点 high を接続します。

（w[low] + diff = w[high] と捉えても良いです。）

接続後のリーダーを返します。

diff は符号付きであることに注意してください。また、low と high がすでに接続されている場合の動作は未定義です。

n = int
ut = PotentializedDisjointSet(Abel).new(n)
ut.unite(low: a, high: b, diff: w) # => leader(a) or leader(b)

Source