オンライン畳み込みで $O(N(\log N)^2) で解く方法を解説します．

\(n\) 頂点の連結無向グラフの総数を \(A_n\) とおきます．

\(A_n\) を，全体から非連結な無向グラフを除外することで計算します．
頂点 \(1\) の所属する連結成分のサイズが \(k\) となるような無向グラフは，

• 連結成分の残りの \(k-1\) 個を選び，
• \(k\) 個の頂点が連結となるようにし，
• 残りの \(n-k\) 個の頂点に適当に辺をはる

ように考えると，

\[ {}_{n-1}C_{k-1} A_k2^{(n-k)(n-k-1)/2} \]

個と計算できます．よって，頂点 \(1\) の所属する連結成分のサイズで場合分けすることで，以下の漸化式が導けます：

\[ \begin{aligned} A_n &= 2^{n(n-1)/2} - \sum_{k=1}^{n-1} {}_{n-1}C_{k-1} A_k2^{(n-k)(n-k-1)/2}\\ &= 2^{n(n-1)/2} - (n-1)!\sum_{k=1}^{n-1} \left(\frac{A_k}{(k-1)!}\right)\left(\frac{2^{(n-k)(n-k-1)/2}}{(n-k)!}\right). \end{aligned} \]

シグマの部分が \(A_1, \dots, A_{n-1}\) を用いた畳み込みの形になっているので，オンライン畳み込みで \(O(N(\log N)^2)\) で解くことができます．