ABC245 F - Endless Walk (500)
いくらでも移動できるということはある点からある点に戻ってくるパスにその点から接続できるということ
自身に入ってくる辺の数を求めておく
入ってくる辺が無い点について以下を行う
DFSを行う
ループ中に訪れた点にまた到達したらループ可能
既にループ可能だと分かっていればそれを返す
自身をループ探索中と記録
自身から行ける点すべてを調べいずれかがループ可能であればそれを選んでループ可能
いずれもループ可能で無ければその点はループ不可能
探索を行っていない点、つまりループになっている点と探索した結果ループしている点に繋がる点の数の和が答え
DFSの呼び出しは$ \mathcal{O}(M)なので全体で$ \mathcal{O}(N+M)
解説の解法
辺を逆向きに張る
入ってくる辺が無い点をキューに入れる
キューが空で無い限り以下を行う
キューから一つ取り出し番号を書く
その点から出ている辺の先について入ってくる辺の数を1減らし、0になったらキューに追加
番号が最後まで書かれていない点の数が答え
途中でループがあればそれらとその上流には番号が書かれない
時間計算量は同じ