Class: UnionFindTree::UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/union_find_tree.rb

Defined Under Namespace

Classes: ParArray, SizeArray

Instance Method Summary collapse

Constructor Details

#initialize ⇒ UnionFind

Returns a new instance of UnionFind.



20
21
22
23
 
# File 'lib/union_find_tree.rb', line 20

def initialize()
  @par = ParArray.new
  @size = SizeArray.new
end

Instance Method Details

#same?(x, y) ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/union_find_tree.rb', line 45

def same?(x, y)
  return find(x) == find(y)
end

#size(x) ⇒ Object 



49
50
51
 
# File 'lib/union_find_tree.rb', line 49

def size(x)
  return @size[find(x)]
end

#unite(x, y) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
 
# 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