突然ですが、次のような連結性を exp/log を用いて扱うテクニックが存在します。

条件 $A$ を満たす連結グラフの個数の指数型母関数 $f(x)$ と、全ての連結成分が条件 $A$ を満たすグラフの個数の指数型母関数 $g(x)$ について、$g(x) = \exp(f(x))$

(ただし、$f(x)$ の定数項は空グラフを認めず $0$、$g(x)$ の定数項は空グラフを認めて $1$ とします。)

証明は https://maspypy.com/%E3%82%B0%E3%83%A9%E3%83%95%E6%95%B0%E3%81%88%E4%B8%8A%E3%81%92#toc4 などをお読みください。

今回の場合、条件 \(A\) は何も要求しないものとすると、\(f(x)\) が求めたいもの、\(g(x)\) は \(N\) 頂点の単純無向グラフの個数の指数型母関数となります。ここで、\(g(x) = \exp(f(x))\) の両辺で \(\log\) を取ると \(\log(g(x)) = \log(\exp(f(x)) = f(x)\) となるため、\(f(x)\) を \(g(x)\) から求めることが出来ます。

\(\log(\exp(f(x)) = f(x)\) についての正当性は https://maspypy.com/%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%83%bb%e5%bd%a2%e5%bc%8f%e7%9a%84%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0-%ef%bc%88%e8%a3%9c%e8%b6%b3%ef%bc%89%e5%ae%9a%e7%be%a9%e3%82%84%e5%bc%8f%e5%a4%89%e5%bd%a2#toc13 などをお読みください。

\(g(x) = \sum_{n \ge 0} \frac{2^{\frac{n(n-1)}{2}}x^n}{n!}\) となるため、\(f(x) = \log(g(x))\) も求めることが出来ます。計算量は \(\mathrm{O}(N \log N)\) です。