結果
問題 | No.556 仁義なきサルたち |
ユーザー |
|
提出日時 | 2017-08-25 17:52:11 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 544 bytes |
コンパイル時間 | 60 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-10-15 15:41:41 |
合計ジャッジ時間 | 3,333 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
コンパイルメッセージ
Syntax OK
ソースコード
def root(uf, i) if uf[i] < 0 i else root(uf, uf[i]) end end def count(uf, i) r = root(uf, i) -uf[r] end def merge(uf, i, j) u = root(uf, i) v = root(uf, j) return if u == v a = count(uf, u) b = count(uf, v) if a > b || (a == b && u < v) uf[v] = u uf[j] = u uf[u] = -(a + b) else uf[u] = v uf[i] = v uf[v] = -(a + b) end end n, m = gets.split.map(&:to_i) uf = [-1] * n m.times do a, b = gets.split.map(&:to_i) merge(uf, a - 1, b - 1) end n.times do |i| p (root(uf, i) + 1) end