グラフに置き換えて連結成分を作る部分までは，公式解説と同様です．

\(\mathrm{dp}[i][j]=\) （\(i\) 番目の連結成分までで使われた頂点の集合が \(j\) である頂点の選び方が存在するかの bool 値）という DP を考え，一度このテーブルを，\(i\) の昇順に全て埋めます．これは連結成分ごとに可能な頂点の選び方を全て試しても \(O(N^2 2^N)\) 時間で行えます．

さて，これをもとに \(\mathrm{dp}_2[i][j] =\)（\(i\) 番目の連結成分までで使われた集合が \(j\) であり，なおかつ最終的に全ての頂点を埋められる可能性のある頂点の選び方が存在するかの bool 値）という DP を新たに定義します．これは先ほどと同様に連結成分ごとに可能な頂点の選び方を全て試し， \(i\) 番目の連結成分で選んだ頂点集合を \(S_i\) として，

• \(\mathrm{dp}[i - 1][j - S_i] = \mathrm{True}\) かつ \(\mathrm{dp}[i][j] = \mathrm{True}\) かつ \(\mathrm{dp}_2[i][j] = \mathrm{True}\) ならば，\(\mathrm{dp}_2[i - 1][j - S_i] = \mathrm{True}\) となるように遷移する

という方法によって，\(i\) の降順に見ていくことにより埋めることが可能です．\(\mathrm{dp}_2\) において \(\mathrm{True}\) で遷移したことのある箇所が，順位として可能な箇所を表します．

以上により，\(O(N^2 2^N)\) 時間でこの問題を解くことができます．

実装例