結果

問題 No.2290 UnUnion Find
ユーザー siman
提出日時 2023-05-07 21:59:15
言語 Ruby
(3.4.1)
結果
AC  
実行時間 569 ms / 2,000 ms
コード長 998 bytes
コンパイル時間 41 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2024-11-24 20:37:10
合計ジャッジ時間 28,895 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:66: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Syntax OK

ソースコード

diff # 

class UnionFind
  def initialize(n)
    @size = Array.new(n, 1)
    @rank = Array.new(n, 0)
    @parent = []

    (0..n).each do |i|
      @parent[i] = i
    end
  end

  def find(x)
    if @parent[x] == x
      x
    else
      @parent[x] = find(@parent[x])
    end
  end

  def unite(x, y)
    x = find(x)
    y = find(y)
    return if x == y

    if x > y
      @parent[x] = y
      @size[y] += @size[x]
    else
      @parent[y] = x
      @size[x] += @size[y]

      @rank[x] += 1 if @rank[x] == @rank[y]
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  def size(x)
    @size[find(x)]
  end
end

N, Q = gets.split.map(&:to_i)
uf = UnionFind.new(N + 1)
cur = 2

Q.times do
  q = gets.split.map(&:to_i)

  case q[0]
  when 1
    u, v = q[1..2].sort
    uf.unite(u, v)

    while uf.find(cur) == 1 && cur <= N
      cur += 1
    end
  when 2
    v = q[1]

    par = uf.find(v)

    if cur > N
      puts -1
    elsif par != 1
      puts 1
    else
      puts cur
    end
  end
end
0