它们中的多少个

解题思路

本题要求 $N$ 个节点构成的且有不超过 $M$ 条割边的无向连通图的数量。

在无向图中，不含割边的极大连通子图就是双连通分量，若将所有双连通分量进行缩点处理，那么所有的双连通分量和割边会构成一个树形结构。

设 $f[i][j]$ 表示 $i$ 个点构成的包含 $j$ 条割边的无向连通图数量

对于计数类 dp，我们通常需要围绕一个基准点来构造一个整体，由于本题所有节点都存在编号，因此我们可以直接以编号为 $1$ 的节点为 “基准点”，枚举 $1$ 号节点所在的双连通分量的大小 $k$，从 $2 \sim i$ 这 $i - 1$ 个节点中选出 $k - 1$ 个，与 $1$ 号点共同构成双连通分量，方案数为 $f[k][0] \* C_{i-1}^{k-1}$

接下来考虑图中其他部分，如果去掉 $1$ 号点所在的双连通分量，那么无向图会分成若干个连通块，从每个连通块出发，都有一条边连接到 $1$ 号点所在的双连通分量上。

设 $g[i][j][k]$ 表示 $i$ 个点构成的、包含 $j$ 条割边的、有 $k$ 个连通块的无向图数量

回到 $f[i][j]$ 的计算，去掉 $1$ 号节点所在的双连通分量后，图中剩余部分的方案数就是 $g[i - k][j - x][x]$，其中 $x$ 是一个正整数，表示图中剩余部分分为 $x$ 个连通块，每个连通块与 $1$ 号节点所在的双连通分量之间的边都是一条割边，所以剩余部分还需要贡献 $j-x$ 条割边。因为 $1$ 号节点所在的双连通分量包含 $k$ 个节点，每个连通块可以连接到这 $k$ 个节点中的任意一个上，所以连接方案有 $k^x$ 种。

综上所述，我们得到 $f[i][j]~(0 < j < i)$ 的状态转移方程：

$$f[i][j] = \sum_{k=1}^{i-1} \big( f[k][0] \* C_{i-1}^{k-1} \* \sum_{x=1}^{min(i-k, j)} g[i-k][j-x][x] \* k^x \big)$$

可以发现起始状态是 $f[i][0]$，即 $i$ 个节点构成的不包含割边的无向连通图数量，我们可以求出 $i$ 个节点构成的无向连通图数量，再减去用 $i$ 个节点构成的包含 $1 \sim i-1$ 条边的连通图数量，就是不包含割边的连通图数量。

设 $h[i]$ 表示 $i$ 个节点的无向连通图数量。

我们先求出 $i$ 个节点构成的无向图总数，再减去 $i$ 个节点构成的不连通图的数量，就是连通图的数量。$i$ 个节点构成的无向图总数为 $2^{i\*(i-1)/2}$，还需要统计 $i$ 个节点构成的不连通图的数量，我们可以枚举编号为 $1$ 的节点所在的连通图包含的节点个数 $k$，从 $2\sim i$ 这 $i-1$ 个节点中选出 $k-1$ 个节点，和 $1$ 号点一起构成大小为 $i$ 的连通块，显然有 $C_{i-1}^{k-1}$ 种选法，剩余 $i-k$ 个节点构成任意无向图，有 $2^{(i-k)\*(i-k-1)/2}$ 种方法。

综上所述，得到 $h[i]$ 的状态转移方程：

$$h[i] = 2^{i \* (i-1)/2} - \sum_{j=1}^{i-1} h[j] \* C_{i-1}^{j-1} \* 2^{(i-j) \* (i-j-1)/2}$$

于是：$f[i][0] = h[i] - \sum_{j=1}^{i-1} f[i][j]$

最后考虑 $g[i][j][k]$ 的计算方法。已编号最小的系欸但所在的连通块为基准，枚举该连通块的大小 $p$ 和 割边数量 $q$，需要从 $i-1$ 个节点中再选出 $p-1$ 个节点构成这个连通块，所以该连通块的方案就有 $f[p][q] \* C_{i-1}^{p-1}$ 种。我们需要从该连通块中选出一个节点，用于与刚才去掉的 $1$ 号节点所在的双连通分量相连，显然有 $p$ 种选法，图中其他部分的方案数就是 $g[i-p][j-q][k-1]$，因此得到方程：

$$g[i][j][k] = \sum_{p=1}^{i} \sum_{q = 0}^{j} f[p][q] \* C_{i-1}^{p-1} \* p \* g[i-p][j-q][k-1]$$

注意：这里算出的 g[i][j][k] 与刚才的定义稍有差别，每个连通块多乘了一个 $p$，用于与计算 $f[i][j]$ 时去掉的 $1$ 号点所在的双连通分量相连，因此我们可以称这些连通块为 “有根” 连通块，这个处理仅限于在本题中，如果抛开本题，单纯计算 “$i$ 个点构成的、包含 $j$ 条割边的、有 $k$ 个连通块的无向图数量”，则不需要乘 $p$

由于 $n$ 个点的无向图最多只有 $n-1$ 条割边，并且我们要求的是割边不超过 $m$ 条的无向连通图数量，所以当 $m \geq n$ 时，我们需要令 $m = n-1$，再进行计算，另外在代码实现中需要注意初值、边界、计算顺序等细节，可以直接看代码。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 55, mod = 1e9 + 7;

int n, m;
int f[N][N]; //设 f[i][j] 表示 i 个节点构成的包含 j 条割边的无向连通图数量
int g[N][N][N]; //设 g[i][j][k] 表示 i 个节点构成的、包含 j 条割边的、有 k 个连通块构成的无向图数量
int h[N]; //设 h[i] 表示 i 个节点的无向连通图数量
int c[N][N]; //c[a][b] 表示组合数 C(a, b)
int pow2[N * N / 2]; //pow2[i] 表示 2 的 i 次方

void init() //预处理 c[][], pow2[]
{
    //预处理 c[][]
    for(int i = 0; i <= n; i++) c[i][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

    //预处理 pow2[]
    pow2[0] = 1;
    for(int i = 1; i <= n * (n - 1) / 2; i++) pow2[i] = pow2[i - 1] * 2 % mod;
}

int main()
{
    scanf("%d%d", &n, &m);
    if(m >= n) m = n - 1;

    init(); //预处理 c[][], pow2[]

    //计数类 dp
    g[0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = pow2[i * (i - 1) / 2];
        for(int j = 1; j < i; j++)
            h[i] = (h[i] - (LL)h[j] * c[i - 1][j - 1] % mod * pow2[(i - j) * (i - j - 1) / 2] % mod) % mod; //h[] 的状态转移方程

        f[i][0] = h[i];
        for(int j = 1; j < i; j++)
        {
            for(int k = 1; k < i; k++)
            {
                int temp = (LL)f[k][0] * c[i - 1][k - 1] % mod; //提前计算循环 x 外的一部分
                int k_x = 1; //记录 k 的 x 次方
                for(int x = 1; x <= min(i - k, j); x++)
                {
                    k_x = (LL)k_x * k % mod;
                    f[i][j] = (f[i][j] + (LL)temp * g[i - k][j - x][x] % mod * k_x % mod) % mod; //f[][] 的状态转移方程
                }
            }
            f[i][0] = (f[i][0] - f[i][j]) % mod;
        }

        for(int j = 0; j < i; j++)
            for(int p = 1; p <= i; p++)
                for(int q = 0; q <= j; q++)
                {
                    int temp = (LL)f[p][q] * c[i - 1][p - 1] % mod * p % mod; //这一部分与 k 无关，在循环 k 外提前计算
                    for(int k = 1; k <= i; k++)
                        g[i][j][k] = (g[i][j][k] + (LL)temp * g[i - p][j - q][k - 1] % mod) % mod; //g[][][] 的状态转移方程
                }
    }

    int res = 0; //记录答案
    for(int i = 0; i <= m; i++) res = (res + f[n][i]) % mod; //要求的是割边不超过 m 的所有连通块数量，从 1 ~ m 累加一下
    printf("%d\n", (res + mod) % mod); //处理一下负余数

    return 0;
}