class NgLib::PotentializedDisjointSet(Abel)

Overview

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

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

Defined in:

nglib/data_structure/potentialized_disjoint_set.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(size : Int) #

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

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

[View source]
def self.new #

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

ut = PotentializedDisjointSet(Abel).new

[View source]

Instance Method Detail

def 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

[View source]
def 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

[View source]
def equiv?(a : Int, b : Int) : Bool #

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

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

[View source]
def groups : Array(Array(Int64)) | Nil #

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

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


[View source]
def 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 の可能性もある)

[View source]
def size(a : Int) : Int64 #

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


[View source]
def 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)

[View source]