読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2222 Alien's Counting

最近出次数1のグラフ問題やりすぎて慣れてしまった

解法

出次数が高々1という制約があるので
TopCoderのSunny Graphと同じように考えると,一つの連結成分は1つの単純閉路といくつかのパスを繋げたような形になります.
閉路について考えると,閉路に含まれる指を曲げると閉路全体を曲げる必要が出てきます.
閉路を一つの頂点としてみることができるので,強連結成分分解をしたい気持ちになります.
で,このグラフを強連結成分分解(というか閉路を一つの頂点としてまとめるだけ)をしてやると,有向辺はその頂点の親ノードを指しているとみることができます.
つまり,辺の向きを逆にしてやればそのまま根付き木になります.
与えられたグラフは森になるので,各根付き木に対して木DPっぽく数え挙げてやって最後に掛け算をすれば答えが出ます.