競技プログラミング用 知識集積所
ABC456E - Endless Holidays
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
「都市iにいる曜日dから休日ループを作れるか？」を深さ優先探索※で探すだけ。
都市と曜日ごとに1つの整数で状態を表し、
- 0：未調査
- 1：ループが成立する
- -1：ループが成立しない
- 2：調査中
とする。
ある都市ある曜日について調べるときには、
- まずその状態を2にする
- 行ける都市全て（自身を含む）について、曜日を1つ進めたデータを見る
- 状態が未調査だったら再帰を1つ潜って探索する
- その中に1つでも状態が1（成立）か2（調査中）があれば、自身の状態を1（成立）にする
- 全ての行先の調査が終わっても2（調査中）から変わっていなければ、-1（不成立）にする
でよい。
全ての都市について曜日0（0-indexで）から深さ優先探索※を走らせ、1ヶ所でも1（成立）という結果になれば、答えはYes。
