JOI 09春合宿 advertisement(難易度8)
問題の構造をよく観察してみる. すると, 閉路がある場合は一つの頂点に置き換えてもよいことがわかる. これを実現するのが
強連結成分分解
である.
強連結成分分解をした後のグラフについて入次数が0の頂点の個数が答えとなる.
実装例:
https://atcoder.jp/contests/joisc2009/submissions/19396753