Codeforces Round #634 F - Robots on a Grid

これを自力ACしました
見た瞬間に方針が立つものの、実装方針を詰める&実装嫌だ〜〜とうだうだする&実装するをしていたらバチャ中に間に合わず、悔しいです...

問題概要

　 $N$ 行 $M$ 列のグリッドグラフが与えられる $(NM\leq 10^6)$ 。グリッドグラフには色と方向が示してある。毎ターン自分のいるマスが示す方向に動くロボットを好きな数設置する。
　ロボットが同じターンに同じマスにいることがないという条件を満たした上で、ロボットを置ける数を最大化するときにロボットを置く黒いマスを最大化しなさい。

解説

　あるマスについて見るとき、そのマスからいける/そのマスにいけるマスの集合は閉路を一つ持つ有向グラフになります。全ての有向グラフに含まれるサイクル長 $p$ の総和がロボットの最大数です。また、サイクル中の適当な点 $P$ を取り出し、有向グラフ中の各点から $P$ との距離を求めます。 $P$ との距離が $mod\ p$ において一致する2組のマスでは、それぞれのマスにおいたロボットは十分大きな時間が経過した後ぶつかるため、両方にロボットを置くことはできません。
　 $P$ との距離を有向グラフ中の全てのマスについて求め、0~p-1 について、 $P$ との距離が $mod\ p$ での剰余と一致する点の中に黒いマスが含まれているかを調べると答えが得られます。