Union Find

union_find1.rb

#簡素版

class UnionFind
  def initialize(size)
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
  end
  
  def unite(x, y)
    x = root(x)
    y = root(y)
    return if x == y

    if @rank[x] > @rank[y]
      @parent[y] = x
    else
      @parent[x] = y
      @rank[y] += 1 if @rank[x] == @rank[y]
    end
  end

  def root(x)
    loop do
      if @parent[x] == x
        return x
      else
        x = @parent[x]
      end
    end
  end

  def same_set?(x, y)
    root(x) == root(y)
  end
  
  def size
    @parent.map { root(_1) }.uniq.size
  end
end

#参考
#https://qiita.com/k_karen/items/5349a25c3eb7b4697f58

union_find2.rb

class UnionFind
  def initialize(data)
    case data
    when Array
      size = data.size
      @map0 = data.map.with_index.to_h
    when Integer
      size = data
      @map0 = size.times.map { [_1, _1] }.to_h
    else
      raise "Error"
    end
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
  end
  
  def unite(x0, y0)
    x = root(x0)
    y = root(y0)
    return if x == y

    if @rank[x] > @rank[y]
      @parent[y] = x
    else
      @parent[x] = y
      @rank[y] += 1 if @rank[x] == @rank[y]
    end
  end

  def root(x0)
    x = @map0[x0]
    loop do
      if @parent[x] == x
        return x
      else
        x = @parent[x]
      end
    end
  end

  def same_set?(x0, y0)
    root(x0) == root(y0)
  end
end