aoj2222:Alien's Counting
解法
入力をグラフだと思ってみる。
こういうタイプのグラフ(各頂点の出次数が高々1)は、単純閉路から木が生えてるみたいな感じになる。
強連結成分は1つの頂点としてみていいので、強連結成分分解する。
すると、グラフは森になる。あとは木dpをする。
結局のところ、この問題は「木の各頂点に0か1を割り当てる。ただし、0を割り当てられた頂点があったとき、その頂点を根とする部分木に含まれる頂点に1が割り当てられていてはならない。このとき、割り当て方の通り数を求めよ」みたいな問題だとわかる。
まあ後は適当に。
初めて強連結成分分解をライブラリとして整備してみました。自分で実装するのはめんどくさいので便利ですね(ただし、可読性が最悪)
