はじめに
AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
今回のお題
AtCoder Beginner Contest C - Connect Cities
Difficulty: 363
今回のテーマ、UnionFind
つい最近、同様の問題 があったり、AtCoder Library Practice Contest があったりとは言え、灰レートは凄いです。
ちなみに、前回はDifficulty: 676でした。
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.select{ _1 < 0 }.size - 1
sub.rb
puts u.parents.select{ _1 < 0 }.size - 1 # 今回
puts -u.parents.min # 前回
前回 --Qiitaの最終行を変更するだけでACします。
sub.rb
@parents = [-3, 0, -2, 2, 0]
前回の入力例 1で説明しますと、u.parentsの中は、u.parents[0]とu.parents[2]が代表の2グループに分けれらますので、それを1つの道路で結べばOK。
AtCoder Library (ACL)のRuby版
ここ --githubで、ACLのRuby版を作成されている動きもあります。
要注目ですね。
| Ruby | |
|---|---|
| コード長 (Byte) | 567 |
| 実行時間 (ms) | 170 |
| メモリ (KB) | 15612 |
まとめ
- ACLBC C を解いた
- Ruby に詳しくなった