class Unionf::UnionFind

Public Class Methods

new(elements) click to toggle source
# File lib/unionf.rb, line 6
def initialize elements
  @id = {}
  @sz = {}
  @el = []
  elements.each {|n| @id[n] = n; @sz[n] = 1; @el << n}
end

Public Instance Methods

connected?(a, b) click to toggle source
# File lib/unionf.rb, line 13
def connected? a, b
  a, b = pair_search a, b
  a == b
end
elements() click to toggle source
# File lib/unionf.rb, line 44
def elements
  @el
end
find(a) click to toggle source
# File lib/unionf.rb, line 30
def find a
  return a if @id[a] == a
  @id[a] = find @id[a]
end
size() click to toggle source
# File lib/unionf.rb, line 35
def size
  @id.size
end
size?(a) click to toggle source
# File lib/unionf.rb, line 39
def size? a
  a = find a
  @sz[a]
end
union(a, b) click to toggle source
# File lib/unionf.rb, line 18
def union a, b
  a, b = pair_search a, b

  return if a == b or a.nil? or b.nil?

  a, b = b, a if @sz[a] > @sz[b]

  @id[a] = b
  @sz[a] += @sz[b]
  @sz[b] = @sz[a]
end

Private Instance Methods