ABC 401-500/ABC435D - Reachability Query 2 - 競技プログラミング用 知識集積所

---

問題

ABC435D

必要知識

B以下レベルの内容は省略

• 幅優先探索※または深さ優先探索※

考え方

ひらめき一発問題。

一度「黒マスへ行ける」になったマスは、二度と「黒マスに行けない」に戻らない。
ということは、クエリ1で単にその頂点を黒く塗るだけでなくその頂点に行けるところ全てを黒く塗ってしまっても実質的に変わらない。
これは、全て逆方向の辺を張ったグラフ上で、指定されたマスから行ける範囲を幅優先探索※または深さ優先探索※調べることで実現できる。

すると、クエリ2ではその頂点の色を答えるだけでよい。

解答例

解答例

注意点

別解