Submission #47534879

---

Source Code Expand

n, q = read_line.split.map(&.to_i)
qs = [] of Tuple(Int32, Int32, Int64)

# 非連結な頂点同士を結ぶ辺のみを抽出したグラフを作成
graph = Array.new(n) { [] of Tuple(Int32, Int64) }
uf = UnionFind.new(n)
q.times do |i|
  a, b, d = read_line.split.map(&.to_i)
  a -= 1
  b -= 1
  qs << {a, b, d.to_i64}
  if !uf.find(a, b)
    uf.union(a, b)
    graph[a] << {b, -d.to_i64}
    graph[b] << {a, d.to_i64}
  end
end

# 各連結成分でBFSしてvalidなXの値（のひとつ）を構築
x = Array.new(n, 0i64)
visited = Array.new(n, false)
n.times do |i|
  next if visited[i]
  que = [i]
  qi = 0
  visited[i] = true
  while qi < que.size
    cur = que[qi]
    qi += 1
    graph[cur].each do |adj, diff|
      if !visited[adj]
        visited[adj] = true
        x[adj] = x[cur] + diff
        que << adj
      end
    end
  end
end

# Xの値のつじつまが合っているものを出力
ans = [] of Int32
q.times do |i|
  a, b, d = qs[i]
  if x[a] - x[b] == d
    ans << i + 1
  end
end
puts ans.join(" ")

class UnionFind
  def initialize(size : Int32)
    @root = Array(Int32).new(size, -1)
  end

  def union(i, j)
    a = root(i)
    b = root(j)
    if a != b
      @root[a] += @root[b]
      @root[b] = a
    end
  end

  def find(i, j)
    root(i) == root(j)
  end

  def root(i)
    return i if @root[i] < 0
    @root[i] = root(@root[i])
  end

  def size(i)
    -@root[root(i)]
  end
end

Submission Info

Compile Error

I: Dependencies are satisfied
I: Building: main

Judge Result