class AcLibraryRb::UnionFind

Disjoint Set Union

Attributes

n[R]
parent_or_size[R]

Public Class Methods

new(n) click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 4
def initialize(n)
  @n = n
  @parent_or_size = Array.new(n, -1)
  # root node: -1 * component size
  # otherwise: parent
end

Public Instance Methods

find(a)
Alias for: leader
groups() click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 43
def groups
  (0 ... @parent_or_size.size).group_by{ |i| leader(i) }.values
end
leader(a) click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 29
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
Also aliased as: root, find
merge(a, b) click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 13
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
Also aliased as: unite
root(a)
Alias for: leader
same(a, b)
Alias for: same?
same?(a, b) click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 24
def same?(a, b)
  leader(a) == leader(b)
end
Also aliased as: same
size(a) click to toggle source
# File lib_lock/ac-library-rb/dsu.rb, line 39
def size(a)
  -@parent_or_size[leader(a)]
end
unite(a, b)
Alias for: merge