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 ]