Class: Unionf::UnionFind

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

Instance Method Summary collapse

Constructor Details

#initialize(elements) ⇒ UnionFind

Returns a new instance of UnionFind.



6
7
8
9
10
11
 
# File 'lib/unionf.rb', line 6

def initialize elements
  @id = {}
  @sz = {}
  @el = []
  elements.each {|n| @id[n] = n; @sz[n] = 1; @el << n}
end

Instance Method Details

#connected?(a, b) ⇒ Boolean

Returns:

  • (Boolean) 


13
14
15
16
 
# File 'lib/unionf.rb', line 13

def connected? a, b
  a, b = pair_search a, b
  a == b
end

#elements ⇒ Object 



44
45
46
 
# File 'lib/unionf.rb', line 44

def elements
  @el
end

#find(a) ⇒ Object 



30
31
32
33
 
# File 'lib/unionf.rb', line 30

def find a
  return a if @id[a] == a
  @id[a] = find @id[a]
end

#size ⇒ Object 



35
36
37
 
# File 'lib/unionf.rb', line 35

def size
  @id.size
end

#size?(a) ⇒ Boolean

Returns:

  • (Boolean) 


39
40
41
42
 
# File 'lib/unionf.rb', line 39

def size? a
  a = find a
  @sz[a]
end

#union(a, b) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
 
# 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