Sha256: c199e7438b2f937515a54ec848ab857f2056bf6e08bb88a56e44891c8308cb71
Contents?: true
Size: 1019 Bytes
Versions: 1
Compression:
Stored size: 1019 Bytes
Contents
module AcLibraryRb # Disjoint Set Union class DSU def initialize(n) @n = n @parent_or_size = Array.new(n, -1) # root node: -1 * component size # otherwise: parent end attr_reader :parent_or_size, :n 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 alias unite merge def same(a, b) leader(a) == leader(b) end alias same? same 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 alias root leader alias find leader def size(a) -@parent_or_size[leader(a)] end def groups (0 ... @parent_or_size.size).group_by{ |i| leader(i) }.values end end UnionFind = DSU end
Version data entries
1 entries across 1 versions & 1 rubygems
Version | Path |
---|---|
ac-library-rb-0.6.0 | lib_lock/ac-library-rb/dsu.rb |