結果

問題 No.1254 補強への架け橋
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2021-02-16 22:00:38
言語 Ruby
(3.4.1)
結果
AC  
実行時間 642 ms / 2,000 ms
コード長 708 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 31,744 KB
最終ジャッジ日時 2024-09-13 10:59:38
合計ジャッジ時間 32,612 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

Edge = Struct.new(:to, :id)
N = gets.to_i
G = Array.new(N + 1){ [] }
(1 .. N).each do |i|
  a,b = gets.split.map(&:to_i)
  G[a] << Edge.new(b, i)
  G[b] << Edge.new(a, i)
end

active = Array.new(N + 1)
parent = Array.new(N + 1)
depth = Array.new(N + 1)

active[N] = G[N].size
parent[N] = N
depth[N] = 0
u = N
loop do
  j = (active[u] -= 1)
  e = G[u][j]
  v = e.to
  
  if j < 0
    u = parent[u]
  elsif !active[v]
    active[v] = G[v].size
    depth[v] = depth[u] + 1
    parent[v] = u
    u = v
  elsif v != parent[u]
    cycle = [e.id]
    w = v
    until w == u
      cycle << G[w][active[w]].id
      w = G[w][active[w]].to
    end
    
    puts cycle.size
    puts cycle.join(" ")
    break
  end
end
0