Union-Find
https://atc001.contest.atcoder.jp/tasks/unionfind_a をACする程度には高速に動作する実装
最適化手法は経路圧縮
code:ruby
class UnionFind
# @param {Integer} n
def initialize(n)
@id = Array.new(n, &:itself)
@sz = Array.new(n, 1)
n.times do |i|
@idi = i
@szi = 1
end
end
def connected?(i, j)
root(i) == root(j)
end
def unite(i, j)
iroot = root(i)
jroot = root(j)
return if iroot == jroot
if @sziroot < @szjroot
@idiroot = j
@szjroot += @sziroot
else
@idjroot = i
@sziroot += @szjroot
end
end
private
def root(i)
if @idi == i
i
else
@idi = @id[@idi] # pass compression
root(@idi)
end
end
end