问题

\(G = (V, E)\) 是一个简单无向图。对于 \(V\) 的每个非空子集 \(S\)，算出 \(G\) 有多少个以 \(S\) 为点集的连通子图。

数据范围：\(|V| \le 17\)。

解

为了方便表述，先介绍一些记号。设 \(G = (V, E)\) 是一个图，\(G\) 的点数记作 \(|G|\)，\(G\) 的边数记作 \(\|G\|\)。对于 \(V'\sube V\)，\(V'\) 导出的 \(G\) 的子图记作 \(G[V']\)。在描述算法的复杂度时，以 \(n\) 表示图的点数，以 \(m\) 表示图的边数。再介绍一个说法，若一个图的点集是 \(V\) 则可称之为 \(V\) 上的图。以下凡言及子图皆指 \(G\) 的子图。

\(S\) 是 \(V\) 的非空子集，定义
\(f(S)\)：\(S\) 上的连通子图的个数；
\(g(S)\)：\(S\) 上的子图的个数。

易见 \(g(S) = 2^{\|G[S]\|}\)，可以在 \(O(m2^n)\) 的时间内算出所有的 \(g(S)\)。

考虑 \(S\) 上的不连通子图的个数，有 \[ f(S) = g(S) - \text{$S$ 上的不连通子图的个数} \] 如何确定 \(S\) 上的不连通子图的个数？有一个的技巧：取 \(S\) 里的一个点 \(v\)，把 \(S\) 上的不连通子图按 \(v\) 所在的连通块的点集 \(T\) 分类。取定 \(v \in S\)，\(S\) 上的不连通子图的个数可表为 \(\sum_{v \in T\subne S} f(T) g(S - T)\)，从而有 \[ f(S) = g(S) - \sum_{v \in T\subne S} f(T) g(S - T) \] \(T \subne S\) 表示 \(T\) 是 \(S\) 的子集且 \(T\ne S\)。可以在 \(O(3^n)\) 的时间内算出所有的 \(f(S)\)。

注

本文是根据 ABC213G Connectivity 2 的官方题解写的。官方题解里说 \(g(S)\) 和 \(f(S)\) 有更快的算法：用快速 Zeta 变换可以在 \(O(n2^n)\) 时间内算出所有的 \(g(S)\)；可以在 \(O(n^22^n)\) 时间内算出所有的 \(f(S)\)。