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