#jSDPlydlt50x5C02. 它们中的多少个 How many of them
它们中的多少个 How many of them
好的,这里我把题目整理为适合上传的形式,包含题目描述、输入输出格式、样例与解释:
题目描述
在无向连通图中,若删除一条边后,图变得不连通,则称该边为割边。
我们要求计算满足如下条件的有标号无向连通图的个数:
- 由 个节点构成,节点编号 。
- 割边的数量不超过 条。
- 图中没有自环和重边。
注意:
- 本题的割边限制为 不超过 条,即割边数量可以是 。
- 与某些在线评测平台上的表述略有不同,此处严格按照题目描述。
你需要输出答案对 取模后的结果。
输入格式
一行,两个整数 和 。
输出格式
一个整数,表示满足条件的无相连通图的数量对 取模后的结果。
数据范围
- (即完全图的边数上界)
输入样例
3 3
输出样例
4
样例解释
个有标号节点,所有割边数不超过 的无向连通图(无自环重边)。
考虑 时,连通图总共有以下 种(割边数量分别为):
-
三角形(3 个节点两两相连)
边集:
割边数量:(任意一条边删除后图依然连通)
满足条件()。 -
链状:1-2-3
边集:
删除边 后不连通 → 割边
删除边 后不连通 → 割边
割边数量:
满足条件()。 -
链状:1-3-2(标号不同)
这是不同的图,因为节点标号不同:
边集:
删除边 不连通 → 割边
删除边 不连通 → 割边
割边数量:
满足条件。 -
链状:2-1-3
边集:
删除边 不连通 → 割边
删除边 不连通 → 割边
割边数量:
满足条件。
验证
时,可能的连通图还有没有其他的?
- 连通图必须最少 条边( 条边是树,树的所有边都是割边)。
- 当 条边时是唯一完全图(无割边)。
- 当 条边时,必须三个点都连通,只能是某个点度为 ,另两个点度为 ,这种结构在标号下共有 种(选择中间那个度为 的点)。
总共有 (三角)+ (三种链)= 种连通图。
其中三种链割边数为 ,三角形割边数为 ,都 ,所以全部满足条件。
因此答案为 。