問題リンク
問題概要
頂点にラベルが振られている\(N\)頂点\(M\)辺の無向グラフであって、以下の条件を満たすものはいくつあるか求めよ。
- 自己ループを持たない
- 全ての頂点の次数が2以下
- 連結成分のサイズの最大値が\(L\)
解法
2番目の条件より、各連結成分については一本道のようなグラフ(o-o-o-...-o-o)か、単純サイクル、もしくは孤立点しかありえない。よって、連結成分のサイズを決めればその中での辺の数と組み合わせは簡単に求まる。
この問題では\(N\)個の頂点をいくつかの連結成分に分割する必要がある。
ここで、この問題を解く着想を得るために、一旦より簡単な次の問題を考える。
{1,2,...,N}をいくつかのグループに分割する方法は何通りあるか。
これは以下のようなDPで解ける。
\(dp[i] = \{1,..,i\}\)の分け方の総数
とおく。\(dp[1]=1\)である。また、このあとの都合上\(dp[0]=1\)とする。
\(dp[i-1]\)までが求まっているとして\( \{1,...,i\}\)の分け方の総数を求める。
\(i\)が属するグループのサイズを\(j (1 \leq j \leq i) \)とすると、
このようなグループのとり方は\( {}_{i-1}C_{j-1} \)通りある。(\(i\)以外の要素を\( \{ 1,...,i-1\}\)から\(j-1\)個とるため)
また、残りの\(i-j\)個の点の分け方は\(dp[i-j]\)通りである。
よって、\(dp[i] = \sum_{j=1}^{i} {}_{i-1}C_{j-1} \times dp[i-j] \)
となる。
元の問題に戻る。
\(dp[i][j][k] \)を
頂点を\(i\)個使って
辺を\(j\)本使って
連結成分の最大値が\(L\)かどうか\( (k=0or1) \)
を満たすようなグラフの総数
として、\(i=1\)から\(N\)まで更新していけば良い。
計算量は\( O(NML) \)になる。
提出
https://atcoder.jp/contests/abc180/submissions/17463080
感想
初1桁が嬉しくて久々に書いた。
