连通 - 点双 / 边双连通变换

这种思想可以帮助我们解决一类点双 / 边双连通子图计数的问题。接下来将会以一些例题举例。

点双连通生成子图计数

题如其名，给出一张 $n$ 个点 $m$ 条边的图，求使得这 $n$ 个点点双连通的边的子集数量。

$n \le 18$。

考虑设计状态 $f_{i, S}$ 表示，$S$ 集合中的点组成的不存在编号 $\le i$ 的割点的连通生成子图个数，以 $i$ 从小到大的顺序转移。

显然当 $i = 0$ 时，$f_{i, S}$ 只要求 $S$ 中的点连通，这是好做的；否则，当 $i \notin S$ 时，$f_{i, S} = f_{i - 1, S}$；那么我们只需考虑 $i \in S$ 的情况。

发现这样的话 $f_{i, S}$ 就是在 $f_{i - 1, S}$ 的基础上 $i$ 也不是割点的情况，这相当于删去 $i$ 后图仍然连通。

反过来考虑，如果我们得知了 $f_{i, *}$ 如何求出 $f_{i - 1, *}$。我们考虑一张 $f_{i - 1, S}$ 中的图，该图删掉点 $i$ 后形成的每个连通块本来都要和点 $i$ 有连边。设其中一个连通块的点集为 $T$，那么这个连通块的总方案数（内部方案数与和 $i$ 连边的方案数）就是 $f_{i, T \cup \{i\}}$。那么我们从 $f_{i, *}$ 得到 $f_{i - 1, *}$ 就可以对于所有 $i \in S$，将 $S$ 中的 $i$ 删去，然后对这些 $S$ 做集合幂级数 $\exp$，最后再将 $i$ 加回来。

那么从 $f_{i - 1, *}$ 得到 $f_{i, *}$ 也是简单的，对于所有 $S \ni i$，将 $S$ 中的 $i$ 删去，然后对这些 $S$ 做集合幂级数 $\ln$，最后再将 $i$ 加回来。

那么算法的瓶颈在于做 $O(n)$ 次集合幂级数 $\ln$，时间复杂度为 $O(n^32^n)$。

大概去感受一下，上述过程就是从只要求图连通的情况逐步变换过来，每一步都在原先的基础上去除一个点是割点的情况，所以我们称这个过程是一个“变换”。

边双连通生成子图计数

题如其名，给出一张 $n$ 个点 $m$ 条边的图，求使得这 $n$ 个点边双连通的边的子集数量。

$n \le 18$。

考虑一个和上一题类似的状态：$f_{i, S}$ 表示，$S$ 集合中的点组成的不存在两个端点编号都 $\le i$ 的割边的连通生成子图个数，以 $i$​ 从小到大的顺序转移。

显然当 $i = 0$ 时，$f_{i, S}$ 只要求 $S$ 中的点连通，这是好做的；否则，当 $i \notin S$ 时，$f_{i, S} = f_{i - 1, S}$；那么我们只需考虑 $i \in S$ 的情况。

反过来考虑，如果我们得知了 $f_{i, *}$ 如何求出 $f_{i - 1, *}$。我们考虑一张 $f_{i - 1, S}$ 中的图，该图删掉存在一个端点编号为 $i$ 且另一个端点编号更小的割边之后会形成若干个连通块，其中恰好有一个连通块包含点 $i$，且其它连通块都要选出恰好一个编号 $< i$ 的点和点 $i$ 连边。设其中一个连通块的点集为 $T$，那么若 $i \in T$，则连通块的方案数为 $f_{i, T}$，否则为 $e(i, T)f_{i, T}$，其中 $e(u, S)$ 表示 $u$ 与点集 $S$ 中编号 $< u$ 的点之间的边数。那么我们从 $f_{i, *}$ 得到 $f_{i - 1, *}$ 就可以对于所有 $i \notin S$，将 $f_{i, S}$ 乘上 $e(i, S)$，然后对这些 $S$ 做集合幂级数 $\exp$，最后用 $i \in S$ 的部分卷上 $i \notin S$ 的部分，并重新使 $i \notin S$ 的 $f_{i - 1, S}$ 继承 $f_{i, S}$。

那么从 $f_{i - 1, *}$ 得到 $f_{i, *}$ 也是简单的，我们知道了所有的 $f_{i - 1, S}$，也就可以推出所有 $i \notin S$ 的 $f_{i, S}$ 以及乘上 $e(i, S)$ 后这些 $S$ 的 $\exp$。对于 $i \in S$ 的部分，卷上 $i \notin S$ 的 $\exp^{-1}$ 即可。

那么算法的瓶颈在于做 $O(n)$ 次集合幂级数 $\exp^{-1}$ 和子集卷积，时间复杂度为 $O(n^32^n)$。

生成仙人掌计数和加强版

题如其名，给出一张 $n$ 个点 $m$ 条边的图，求使得这 $n$ 个点构成一棵仙人掌的边的子集数量。

$n \le 18$。

考虑设计状态 $f_{i, S}$ 表示，$S$ 集合中的点组成的只存在编号 $\le i$ 的割点的生成仙人掌个数，以 $i$ 从小到大的顺序转移。

显然当 $i = 0$ 时，$f_{i, S}$ 要求 $S$ 中的点必须是一个环（单点或者只有一条边也算），这是好做的；否则，当 $i \notin S$ 时，$f_{i, S} = f_{i - 1, S}$；那么我们只需考虑 $i \in S$ 的情况。

我们考虑一张 $f_{i, S}$ 中的仙人掌，将点 $i$ 删去后会分裂成若干个连通块。设其中一个连通块的点集为 $T$，那么这个连通块的总方案数（内部方案数与和 $i$ 连边的方案数）就是 $f_{i - 1, T \cup \{i\}}$。在 $T \cup \{i\}$ 的这些点中，$i$ 不能是割点，否则删掉点 $i$ 后 $T$ 中的点不连通，其它的点没有影响。那么我们从 $f_{i - 1, *}$ 得到 $f_{i, *}$ 就可以对于所有 $i \in S$，将 $S$ 中的 $i$ 删去，然后对这些 $S$ 做集合幂级数 $\exp$，最后再将 $i$ 加回来。

那么算法的瓶颈在于做 $O(n)$ 次集合幂级数 $\exp$，时间复杂度为 $O(n^32^n)$。

顺带提一嘴，这样做也可以对每个点集求出生成树数量，但是这玩意和对每个子集暴力上矩阵树定理的时间复杂度是一样的……