Class: DSA::UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/union_find.rb

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ UnionFind

Returns a new instance of UnionFind.



3
4
5
6
7
 
# File 'lib/dsa-ruby/union_find.rb', line 3

def initialize(n)
  @parent = (0...n).to_a
  @rank = Array.new(n, 0)
  @count = n
end

Instance Method Details

#connected?(x, y) ⇒ Boolean

Returns:

  • (Boolean) 


38
39
40
 
# File 'lib/dsa-ruby/union_find.rb', line 38

def connected?(x, y)
  find(x) == find(y)
end

#count ⇒ Object 



42
43
44
 
# File 'lib/dsa-ruby/union_find.rb', line 42

def count
  @count
end

#find(x) ⇒ Object

Raises:

  • (IndexError) 


9
10
11
12
13
14
 
# File 'lib/dsa-ruby/union_find.rb', line 9

def find(x)
  raise IndexError, "index out of bounds" if x < 0 || x >= @parent.size

  @parent[x] = find(@parent[x]) if @parent[x] != x
  @parent[x]
end

#size ⇒ Object 



46
47
48
 
# File 'lib/dsa-ruby/union_find.rb', line 46

def size
  @parent.size
end

#union(x, y) ⇒ Object

Raises:

  • (IndexError) 


16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/dsa-ruby/union_find.rb', line 16

def union(x, y)
  raise IndexError, "index out of bounds" if x < 0 || x >= @parent.size
  raise IndexError, "index out of bounds" if y < 0 || y >= @parent.size

  root_x = find(x)
  root_y = find(y)

  return false if root_x == root_y

  if @rank[root_x] < @rank[root_y]
    @parent[root_x] = root_y
  elsif @rank[root_x] > @rank[root_y]
    @parent[root_y] = root_x
  else
    @parent[root_y] = root_x
    @rank[root_x] += 1
  end

  @count -= 1
  true
end