UnionFind木(簡易版/ruby)

すこし忘れていたのでメモ
rootで親をつなぎかえるのが肝。

class UnionFind < Array
    def initialize(n)
        super(n){|i| i}
    end
    def root(i)
        self[i] == i ? i : self[i] = root(self[i])
    end
    def unite(i,j)
        self[root(i)] = root(j)
    end
    def same?(i,j)
        root(i) == root(j)
    end
end

参考

www.slideshare.net