class UnionFindTree::UnionFind
Public Class Methods
new()
click to toggle source
# File lib/union_find_tree.rb, line 20 def initialize() @par = ParArray.new @size = SizeArray.new end
Public Instance Methods
same?(x, y)
click to toggle source
# File lib/union_find_tree.rb, line 45 def same?(x, y) return find(x) == find(y) end
size(x)
click to toggle source
# File lib/union_find_tree.rb, line 49 def size(x) return @size[find(x)] end
unite(x, y)
click to toggle source
# File lib/union_find_tree.rb, line 34 def unite(x, y) x = find(x) y = find(y) return nil if x == y x, y = y, x if @size[x] < @size[y] @par[y] = x @size[x] += @size[y] end
Private Instance Methods
find(x)
click to toggle source
# File lib/union_find_tree.rb, line 27 def find(x) return x if x == @par[x] return @par[x] = find(@par[x]) end