Class: DSA::UnionFind

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

Overview

DSA::UnionFind - Disjoint-set data structure with path compression and union by rank.

Tracks a set of elements partitioned into disjoint subsets. Supports efficient union and find operations.

Examples:

uf = DSA::UnionFind.new(10)
uf.union(1, 2)
uf.union(2, 3)
uf.connected?(1, 3)  # => true
uf.count              # => 8 (started with 10, merged 2 pairs)

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ DSA::UnionFind

Initialize a new UnionFind structure with n disjoint sets.

Examples:

uf = DSA::UnionFind.new(10)

Parameters:

  • n (Integer) —

    the number of elements (0 to n-1), each in its own set



19
20
21
22
23
 
# File 'lib/dsa-ruby/union_find.rb', line 19

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

Instance Method Details

#connected?(x, y) ⇒ Boolean

Checks if two elements are in the same set.

Examples:

uf.union(1, 2)
uf.connected?(1, 2)  # => true
uf.connected?(1, 3)  # => false

Parameters:

  • x (Integer) —

    the first element

  • y (Integer) —

    the second element

Returns:

  • (Boolean) —

    true if x and y are in the same set



81
82
83
 
# File 'lib/dsa-ruby/union_find.rb', line 81

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

#count ⇒ Integer

Returns the number of disjoint sets.

Examples:

uf = DSA::UnionFind.new(10)
uf.union(1, 2)
uf.count  # => 9

Returns:

  • (Integer) —

    the number of disjoint sets



92
93
94
 
# File 'lib/dsa-ruby/union_find.rb', line 92

def count
  @count
end

#find(x) ⇒ Integer

Finds the root of the set containing element x, with path compression.

Examples:

uf.union(1, 2)
uf.find(2)  # => root of the set containing 1 and 2

Parameters:

  • x (Integer) —

    the element to find

Returns:

  • (Integer) —

    the root of the set containing x

Raises:

  • (IndexError) —

    if x is out of bounds



33
34
35
36
37
38
 
# File 'lib/dsa-ruby/union_find.rb', line 33

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 ⇒ Integer

Returns the total number of elements.

Examples:

uf = DSA::UnionFind.new(10)
uf.size  # => 10

Returns:

  • (Integer) —

    the number of elements (0 to n-1)



102
103
104
 
# File 'lib/dsa-ruby/union_find.rb', line 102

def size
  @parent.size
end

#union(x, y) ⇒ Boolean

Merges the sets containing elements x and y.

Examples:

uf.union(1, 2)  # => true
uf.union(2, 3)  # => true
uf.union(1, 3)  # => false (already connected)

Parameters:

  • x (Integer) —

    the first element

  • y (Integer) —

    the second element

Returns:

  • (Boolean) —

    true if the sets were merged, false if already connected

Raises:

  • (IndexError) —

    if x or y is out of bounds



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/dsa-ruby/union_find.rb', line 50

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