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