ABC 401-500/ABC446F - Reachable Set 2 - 競技プログラミング用 知識集積所

---

問題

ABC446F

必要知識

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

• 隣接リスト※
• 幅優先探索※または深さ優先探索※（ただし、通常のものではなく、条件付きで実行する特殊なやつ）

考え方

基本的には幅優先探索※または深さ優先探索※。
ただし、頂点番号が指定の数以上の点では必ずストップするという制約付きで実行する。
その条件下で番号がその数以下の全ての頂点にたどり着けるなら答えはその数より大きい番号の到達可能頂点数、そうでないなら-1である。

まず、頂点0のみを到達可能頂点としておく。
頂点iについて調査するときには、

• 頂点iが到達可能頂点なら、そこから条件付き幅優先探索※で、新たに到達可能になる頂点を探して追加する。
• 頂点iが到達可能頂点でないなら、何もしない。
• その後、i以下のところが全て到達可能なら、到達可能頂点数からi+1を引いて答える。

を頂点0から順に実行していけばよい。

高速化の工夫として、

• 条件付き幅優先探索※のとき、すでにそこから先を調査済の頂点を見つけたら、そこから先への深入りを止める。
• i以下のところが全て到達可能かどうかは、前の調査結果をうまく使いまわす

を行えば、全ての頂点と辺を1回ずつしか見ないので、O(N+M)で計算量的にも間に合う。

解答例

解答例

注意点

別解