#jSDPlydlt50x5C02. 它们中的多少个 How many of them

它们中的多少个 How many of them

好的,这里我把题目整理为适合上传的形式,包含题目描述、输入输出格式、样例与解释:


题目描述

在无向连通图中,若删除一条边后,图变得不连通,则称该边为割边

我们要求计算满足如下条件的有标号无向连通图的个数:

  1. NN 个节点构成,节点编号 1N1 \sim N
  2. 割边的数量不超过 MM
  3. 图中没有自环和重边。

注意:

  • 本题的割边限制为 不超过 MM,即割边数量可以是 0,1,,M0,1,\dots,M
  • 与某些在线评测平台上的表述略有不同,此处严格按照题目描述。

你需要输出答案对 109+710^9 + 7 取模后的结果。


输入格式

一行,两个整数 NNMM

输出格式

一个整数,表示满足条件的无相连通图的数量对 109+710^9+7 取模后的结果。


数据范围

  • 2N502 \le N \le 50
  • 0MN(N1)20 \le M \le \dfrac{N(N-1)}{2}(即完全图的边数上界)

输入样例

3 3

输出样例

4

样例解释

N=3N=3 个有标号节点,所有割边数不超过 33 的无向连通图(无自环重边)。

考虑 N=3N=3 时,连通图总共有以下 44 种(割边数量分别为):

  1. 三角形(3 个节点两两相连)
    边集:{(1,2),(2,3),(1,3)}\{(1,2),(2,3),(1,3)\}
    割边数量:00(任意一条边删除后图依然连通)
    满足条件(030 \le 3)。

  2. 链状:1-2-3
    边集:{(1,2),(2,3)}\{(1,2),(2,3)\}
    删除边 (1,2)(1,2) 后不连通 → 割边
    删除边 (2,3)(2,3) 后不连通 → 割边
    割边数量:22
    满足条件(232 \le 3)。

  3. 链状:1-3-2(标号不同)
    这是不同的图,因为节点标号不同:
    边集:{(1,3),(2,3)}\{(1,3),(2,3)\}
    删除边 (1,3)(1,3) 不连通 → 割边
    删除边 (2,3)(2,3) 不连通 → 割边
    割边数量:22
    满足条件。

  4. 链状:2-1-3
    边集:{(1,2),(1,3)}\{(1,2),(1,3)\}
    删除边 (1,2)(1,2) 不连通 → 割边
    删除边 (1,3)(1,3) 不连通 → 割边
    割边数量:22
    满足条件。


验证

N=3N=3 时,可能的连通图还有没有其他的?

  • 连通图必须最少 22 条边(N1N-1 条边是树,树的所有边都是割边)。
  • 33 条边时是唯一完全图(无割边)。
  • 22 条边时,必须三个点都连通,只能是某个点度为 22,另两个点度为 11,这种结构在标号下共有 33 种(选择中间那个度为 22 的点)。

总共有 11(三角)+ 33(三种链)= 44 种连通图。
其中三种链割边数为 22,三角形割边数为 00,都 3\le 3,所以全部满足条件。

因此答案为 44