Class: DSU

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

Overview

Disjoint Set Union

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n = 0) ⇒ DSU

Returns a new instance of DSU.



3
4
5
6
7
8
 
# File 'lib/dsu.rb', line 3

def initialize(n = 0)
  @n = n
  @parent_or_size = Array.new(n, -1)
  # root node: -1 * component size
  # otherwise: parent
end

Instance Attribute Details

#n ⇒ Object (readonly)

Returns the value of attribute n.



10
11
12
 
# File 'lib/dsu.rb', line 10

def n
  @n
end

#parent_or_size ⇒ Object (readonly)

Returns the value of attribute parent_or_size.



10
11
12
 
# File 'lib/dsu.rb', line 10

def parent_or_size
  @parent_or_size
end

Instance Method Details

#[](a) ⇒ Object 



38
39
40
41
42
43
44
45
 
# File 'lib/dsu.rb', line 38

def [](a)
  if @n <= a
    @parent_or_size.concat([-1] * (a - @n + 1))
    @n = @parent_or_size.size
  end

  @parent_or_size[a] < 0 ? a : (@parent_or_size[a] = self[@parent_or_size[a]])
end

#groups ⇒ Object 



51
52
53
 
# File 'lib/dsu.rb', line 51

def groups
  (0 ... @parent_or_size.size).group_by{ |i| leader(i) }.values
end

#leader(a) ⇒ Object Also known as: root, find 



28
29
30
31
32
33
34
 
# File 'lib/dsu.rb', line 28

def leader(a)
  unless 0 <= a && a < @n
    raise ArgumentError.new, "#{a} is out of range (0...#{@n})"
  end

  @parent_or_size[a] < 0 ? a : (@parent_or_size[a] = leader(@parent_or_size[a]))
end

#merge(a, b) ⇒ Object Also known as: unite 



12
13
14
15
16
17
18
19
20
 
# File 'lib/dsu.rb', line 12

def merge(a, b)
  x = leader(a)
  y = leader(b)
  return x if x == y

  x, y = y, x if -@parent_or_size[x] < -@parent_or_size[y]
  @parent_or_size[x] += @parent_or_size[y]
  @parent_or_size[y] = x
end

#same?(a, b) ⇒ Boolean Also known as: same

Returns:

  • (Boolean) 


23
24
25
 
# File 'lib/dsu.rb', line 23

def same?(a, b)
  leader(a) == leader(b)
end

#size(a) ⇒ Object 



47
48
49
 
# File 'lib/dsu.rb', line 47

def size(a)
  -@parent_or_size[leader(a)]
end

#to_s ⇒ Object 



55
56
57
 
# File 'lib/dsu.rb', line 55

def to_s
  "<#{self.class}: @n=#{@n}, #{@parent_or_size}>"
end