🌳
[ABC304 E] Good Graph
根に変換して考える問題。
例1で問題文を理解する
グラフ編
このグラフは、
次の経路がないことが保証されている。
その状態を「良いグラフ」と言う。
何かして良いグラフにするのではなく、もともと良いグラフである。
クエリ編
続いて次の辺を繋いでも「良いグラフ」を維持しているか？ に答える。
| 辺 |
|---|
| 2-5 |
| 2-6 |
| 5-6 |
| 5-4 |
重要なのは、繋ぐ操作が独立しているということ。順番に連結していくのではない。
解法シミュレーション
繋がっていてはいけない経路を「禁止経路」と呼ぶことにする。そして、辺の節を根に変換する。
| 禁止経路 | 根-根 |
|---|---|
| 1-5 | 2-4 |
| 2-6 | 2-6 |
| 4-3 | 2-4 |
そしてクエリの一つめで考えると、
- 2-5 を根に変換すると 2-4 になる
- 2-4 は禁止経路に含まれる
- ということは、もし 2-5 を繋いでしまうと「根2の木」と「根4の木」が繋がってしまう
- 2-4 が繋がると禁止経路 1-5 4-3 も繋がる
- したがって辺 2-5 を繋げてしまうと良いグラフではなくなる = No
クエリの三つめで考えると、
- 5-6 を根に変換すると 4-6 になる
- 4-6 は禁止経路に含まれない
- ということは、5-6 を繋いでも禁止経路は維持されたままである
- したがって辺 2-5 を繋げても良いグラフのままである = Yes
まとめると、
| 辺 | 根-根 | 禁止経路に含れない？ |
|---|---|---|
| 2-5 | 2-4 | No |
| 2-6 | 2-6 | No |
| 5-6 | 4-6 | Yes |
| 5-4 | 4-4 | Yes |
となる。
コード (AC)
N, M = gets.split.collect(&:to_i) # => [6, 6]
UV = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 3], [3, 1], [5, 4], [5, 5]]
K = gets.to_i # => 3
XY = K.times.collect { gets.split.collect(&:to_i) } # => [[1, 5], [2, 6], [4, 3]]
Q = gets.to_i # => 4
PQ = Q.times.collect { gets.split.collect(&:to_i) } # => [[2, 5], [2, 6], [5, 6], [5, 4]]
ds = DisjointSet[UV] # => 親:{1=>2, 2=>2, 3=>2, 5=>4, 4=>4} 構図:{2=>[1, 2, 3], 4=>[5, 4]} 節数:{2=>3, 4=>2} 木数:2 高さ:{2=>2, 4=>2}
pair = -> (x, y) { [ds.root(x), ds.root(y)].sort }
ignore = XY.collect { |e| pair[*e] }.to_set # => #<Set: {[2, 4], [2, 6]}>
ans = PQ.collect { |e| !ignore.include?(pair[*e]) } # => [false, false, true, true]
puts ans.collect { |e| e ? "Yes" : "No" }
Discussion