ABC245 : AtCoder Beginner Contest 245 F - Endless Walk を解いた。
解いたときに考えたことを書く。本番では解けなかった。時間があれば解けたかもしれない。
問題: https://atcoder.jp/contests/abc245/tasks/abc245_f
有向グラフ G において閉路を構成する頂点と閉路につながる頂点の個数を求める。
各頂点からの経路で閉路を検出しようとすると間に合わない。閉路に繋がるものも含むのでなかなか難しい。
逆にまったく対象外の頂点を数えてみる。たとえば出次数が 0 のものは条件を満たせない。条件を満たせない頂点だけに繋がる頂点もそうだろう。これを繰り返せば良さそうだ。単純に頂点をひとつずつ確定しようとすると間に合わない。
実際には毎回すべての頂点を走査する必要はなくて確定した頂点へと繋がっている頂点を順に調べれば良い。辺は 1 回ずつしか走査しなくて良い。これなら間に合う。最初にすべての頂点を走査して出次数が 0 のものを enqueue する。あとは確定した頂点へと伸びる辺を辿って消していく。辺を消したときに出次数が 0 なら enqueue する。確定した頂点の数を全体の頂点数から引けば答えになる……はず。
解説: https://atcoder.jp/contests/abc245/editorial/3652 提出: https://atcoder.jp/contests/abc245/submissions/30949130
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit
