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
pair_search(a, b)
click to toggle source
# File lib/unionf.rb, line 50 def pair_search a, b a = find a b = find b [a,b] end