Ruby で解く AtCoder ABC177 D UnionFind

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Friends
Difficulty: 676

今回のテーマ、UnionFind

典型問題の B - Union Find - AtCoder の応用です。

Ruby

ruby.rb

class UnionFind
  def initialize(n)
    @parents = Array.new(n, -1)
  end
  def find(x)
    @parents[x] < 0 ? x : @parents[x] = find(@parents[x])
  end
  def parents
    @parents
  end
  def union(x, y)
    x = find(x)
    y = find(y)
    return if x == y
    if @parents[x] > @parents[y]
      x, y = y, x
    end
    @parents[x] += @parents[y]
    @parents[y] = x
  end  
end

n, m = gets.split.map(&:to_i)
u = UnionFind.new(n)
m.times do
  a, b = gets.split.map(&:to_i)
  u.union(a - 1, b - 1)
end
puts -u.parents.min

sub.rb

    @parents = Array.new(n, -1)

    @parents[x] += @parents[y]

配列@parentsに初期値-1を代入します。
次に、ペアとなった配列の初期値-1を加算します。
これを繰り返すことで、ペアの集合の要素数を取得することができます。

sub.rb

@parents = [-3, 0, -2, 2, 0]

入力例 1の場合、マイナスの数値を見ますと、3と2のグループに分かれることが分かります。
よって出力は、グループの要素が大きい方の3になります。

	Ruby
コード長 (Byte)	548
実行時間 (ms)	260
メモリ (KB)	15824

まとめ

• ABC 177 D を解いた
• Ruby に詳しくなった

参照したサイト
AtCoder Beginner Contest 177 参戦記