桥必须保留,每个简单环恰好断掉一条边 —— 答案就是所有环长的乘积。
(GESP202609 八级)给定一张有 n 个顶点 m 条边的无向连通图 G,顶点依次以 1, 2, … , n 编号。G 有以下特殊的性质:
G 中的每条边至多属于一个简单环;G 中没有重边与自环。简单环是指环中顶点互不相同,且不经过重复边的回路。
请你求出 G 的不同生成树的数量。两棵生成树不同,当且仅当存在一条边在其中一棵生成树中出现,而不在另一棵生成树中出现。由于答案可能很大,你只要求出答案对 998244353 取模的结果。
输入格式:第一行两个正整数 n, m,分别表示 G 的顶点数与边数;接下来 m 行,每行两个整数 uᵢ, vᵢ,表示一条连接顶点 uᵢ, vᵢ 的无向边。
输出格式:输出一行一个整数,表示 G 的不同生成树的数量对 998244353 取模的结果。
子任务:
| 数据点 | 限制 |
|---|---|
| 40% | 1 ≤ n ≤ 8,1 ≤ m ≤ 10 |
| 60% | 1 ≤ n ≤ 2000,1 ≤ m ≤ 2000 |
| 全部 | 1 ≤ n ≤ 10⁵,1 ≤ m ≤ 10⁵ |
k 的环就贡献 k 种选择;各环互不干扰,所以总方案数 = 所有环长的乘积。仙人掌图生成树计数桥必留 + 每环断一条答案 = Π 环长DFS 回边判环迭代写法防爆栈取模 998244353
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m;随后 m 行每行 uᵢ, vᵢ 表示一条无向边 |
| 输出 | 生成树数量对 998244353 取模 |
| 图的性质 | 连通、无向、无重边、无自环 |
| 关键限制 | 每条边至多属于一个简单环(仙人掌) |
| 数据范围 | 1 ≤ n, m ≤ 10⁵ |
| 部分分 | 40% 保证 n ≤ 8;60% 保证 n ≤ 2000 |
k 条边,如果一条都不删,环上就会出现回路,不是树;而只要删掉任意一条,环就被"拉直",再没有回路,所以每个环的选择数恰好是它的长度 k(u, w)(w 是 u 的祖先)恰好对应一条基本环,环长 = depth[u] − depth[w] + 1。在仙人掌里这些基本环正好就是全部简单环,且两两边不相交,直接逐个乘起来就行,不用去重n 可以到 10⁵,图退化成一条长链时递归深度就是 10⁵,会栈溢出(RE),所以要用手写栈的迭代版本样例 1 长这样:
7 8 1 2 2 3 3 1 3 4 4 5 5 6 6 7 7 4
期望输出 12。我们先把图拆开看:
| 组成部分 | 边 | 类型 | 环长 / 是否必留 |
|---|---|---|---|
| 环 A | 1–2, 2–3, 3–1 | 长度为 3 的简单环 | 环长 3 → 3 种断法 |
| 桥 | 3–4 | 桥 | 必须留在生成树里 |
| 环 B | 4–5, 5–6, 6–7, 7–4 | 长度为 4 的简单环 | 环长 4 → 4 种断法 |
图上一共 7 个顶点,生成树需要 7 − 1 = 6 条边
边 3–4 是桥:删掉它,{1,2,3} 与 {4,5,6,7} 就断开了
所以 3–4 必须选,占掉 1 个名额
✅ 桥 3–4 一定在树里
环 A 有 3 条边:1–2、2–3、3–1
若三条全留,就形成回路 → 不是树
断掉任意一条,环被拉直,剩下 2 条边把 1、2、3 连成一棵树
可选的断法有 3 条 → 3 种方案
✅ 环 A 贡献 3
环 B 有 4 条边:4–5、5–6、6–7、7–4
同理必须且只需断一条,可选断法有 4 条
环 A 与环 B 不共享任何一条边(只通过桥 3–4 相连)
所以两者的选择互相独立
✅ 环 B 贡献 4
总方案数 = 3 × 4 = 12
边数校验:桥 1 条 + 环 A 留 2 条 + 环 B 留 3 条 = 6 条 = n − 1 ✓
顶点数校验:7 个顶点、6 条边且连通无环 → 确实是生成树 ✓
✅ 答案 12
3 × 4 = 12 ✓
| DFS 顺序 | 回边 (u, w) | depth[u] | depth[w] | 环长 = depth[u] − depth[w] + 1 |
|---|---|---|---|---|
| 1 → 2 → 3 | 3 → 1 | 2 | 0 | 2 − 0 + 1 = 3 |
| 3 → 4 → 5 → 6 → 7 | 7 → 4 | 5 | 2 | 5 − 2 + 1 = 4 |
depth[w] < depth[u]:被访问过且深度更小,说明 w 在 u 的上方,这是一条回边;反过来 depth[w] > depth[u] 的那些,是同一个环从另一头被看到,必须跳过,否则同一个环会被算两次。样例 2 是一棵没有环的树:
5 4 1 2 1 3 2 4 2 5
期望输出 1。整张图没有简单环,所有边都是桥、都必须留下,而 n − 1 = 4 条边恰好就是全部边 —— 只有唯一一棵生成树。用"乘积"的视角看:没有任何环参与相乘,空乘积 = 1,和答案一致。
| 图的样子 | 环的个数 | 答案 = Π 环长 |
|---|---|---|
| 一棵树(无环) | 0 个 | 1(空乘积) |
| 一个长度为 k 的环 | 1 个 | k |
| 一个 3-环 + 一个 4-环(样例 1) | 2 个 | 3 × 4 = 12 |
| n = 1, m = 0(只有一个孤立点) | 0 个 | 1 |
题目说"每条边至多属于一个简单环"
也就是说:任何一条边,不可能同时被两个不同的简单环用到
两个环最多只能共享一个顶点(像两个圆相切的切点)
这正是"仙人掌"这个名字的由来
✅ 环与环的边集合互不相交
无向图 DFS 中,每条回边 (u, w) 与"树上从 w 到 u 的路径"
合起来构成一个基本环
不同回边对应的基本环,树边部分天然不重叠
(否则某条树边就会落在两个基本环里,与仙人掌性质矛盾)
✅ 基本环 = 全部简单环,两两不交
一般图上"回边个数"远多于"简单环个数",需要去重
但仙人掌上,回边与简单环一一对应
所以 DFS 每发现一条回边就乘一次,
既不会漏、也不会重复
✅ 不用任何去重逻辑
K₄(4 个点两两相连,6 条边),它的生成树有 16 棵,而"环长乘积"这种算法算不出 16——因为一条边同时属于多个环,各环的"断一条"决策不再独立,必须用基尔霍夫矩阵树定理(行列式 / 高斯消元)才能算。c 个简单环,环长分别为 k₁, k₂, … , k_c,则 m = (n − 1) + c(生成树 n−1 条边 + 每个环多出 1 条边)。仙人掌的结构完全由"树骨架 + 每个环上多出来的那一条边"决定。n = 1, m = 0 或树的情形答案是 1:c = 0,空乘积自然是 1。一次 DFS,遇到回边就乘上 (depth[u] − depth[w] + 1),最后取模
Π 环长;而 DFS 的回边与简单环一一对应,所以数回边 = 数环。两个观察咬合上,一行乘法就结束了。构造拉普拉斯矩阵,删掉一行一列后求行列式
O(n³)(高斯消元)n ≤ 2000 时才能勉强跑n = 10⁵ 时完全不可行10⁵ 的行列式根本算不动,只能拿 60 分的部分分。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 迭代 DFS + Π 环长 | O(n + m) | ✅ 正解,能拿满分 |
| 矩阵树定理(高斯消元) | O(n³) | ⚠️ 只对 n ≤ 2000 的部分分有效 |
| 枚举所有 n − 1 条边子集 | C(m, n−1),指数级 | ❌ 40 分暴力专用 |
第一行输入 n 与 m,随后 m 行每行一条无向边 u v(保证是仙人掌)。程序用迭代 DFS 找出所有基本环并相乘。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MOD = 998244353; const int MAXN = 100005; int head[MAXN], nxt[MAXN * 2], to[MAXN * 2], ecnt; void addEdge(int u, int v) { to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt; to[++ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt; } int dep[MAXN]; bool vis[MAXN]; int stNode[MAXN], stPar[MAXN], stIt[MAXN]; // 手写栈:结点 / 父结点 / 邻接表指针 int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); addEdge(u, v); } long long ans = 1; // 空乘积 = 1(无环时答案就是 1) for (int s = 1; s <= n; s++) { if (vis[s]) continue; vis[s] = true; dep[s] = 0; int top = 0; stNode[top] = s; stPar[top] = 0; stIt[top] = head[s]; top++; while (top > 0) { int u = stNode[top - 1]; if (stIt[top - 1] == 0) { top--; continue; } // u 的边扫完了,出栈 int e = stIt[top - 1]; stIt[top - 1] = nxt[e]; // 指向下一条边 int w = to[e], p = stPar[top - 1]; if (w == p) continue; // 不走父边(无重边) if (vis[w]) { // w 已被访问:只有 depth[w] < depth[u] 才是"回边",一个环只算一次 if (dep[w] < dep[u]) ans = ans * (dep[u] - dep[w] + 1) % MOD; } else { vis[w] = true; dep[w] = dep[u] + 1; stNode[top] = w; stPar[top] = u; stIt[top] = head[w]; top++; } } } printf("%lld\n", ans); return 0; }
dep[w] < dep[u] 判定回边(保证一个环只乘一次);② ans = ans * (dep[u] − dep[w] + 1) % MOD 是"环长";③ ans 初值为 1,这样无环时输出 1,正是题目样例 2 的答案。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (w == p) continue; | 跳过父边 | 无向边存了两遍,不走回去才是一棵搜索树 |
if (vis[w] && dep[w] < dep[u]) | 识别回边 | 保证每个环只被统计一次(从深度大的那头看) |
dep[u] - dep[w] + 1 | 基本环长度 | 树上 w→u 的路径有 dep[u] − dep[w] 条边,加上回边本身 |
ans * (…) % MOD | 累乘取模 | 各环独立,用乘法原理;边乘边取模防溢出 |
手写栈 stNode/stPar/stIt | 迭代 DFS | n = 10⁵ 的长链会让递归爆栈,必须迭代 |
n = 10⁵ 时必 RE);② 忘记判断 dep[w] < dep[u],同一个环被乘两次(答案平方);③ ans 初值写成 0,无环时输出 0 而不是 1;④ 乘法不开 long long(ans 可达 10⁹、环长可达 10⁵,乘积约 10¹⁴,int 溢出);⑤ 邻接表只加单向边,导致 DFS 遍历不到整个图。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
7 8 | 12 | 题面样例 1:环长 3 与 4,3 × 4 = 12 |
5 4 | 1 | 题面样例 2:无环(树),空乘积 = 1 |
3 3 | 3 | 单个三角形:环长 3 → 3 |
4 4 | 4 | 单个 4-环:环长 4 → 4 |
5 6 | 9 | 两个 3-环共享顶点 1:3 × 3 = 9 |
4 3 | 1 | 一条链(全是桥):唯一生成树 |
1 0 | 1 | 只有一个顶点:唯一的空树,答案 1 |
8 9 | 15 | 3-环与 5-环用桥相连:3 × 5 = 15 |
dep[w] < dep[u] 吗?③ ans 初值是 1 吗?④ 每一步都取模了吗?n = 10⁵ 的长链会让递归深度到 10⁵,务必改写成手写栈的迭代版本。if (vis[w]) 就乘,会把环从两头各看一次,必须加上 dep[w] < dep[u]。ans 与环长相乘可达约 10¹⁴,必须用 long long。O(m)O(n + m)O(1),乘法总次数 ≤ mO(n + m),n = m = 10⁵ 时只有约 2 × 10⁵ 次操作邻接表用"链式前向星"存 2m 条有向边,配 head / nxt / to 三个长度为 2m + 1 的数组;另外还有 dep、vis 与长度 n 的手写栈,总空间 O(n + m)。
✅ 线性复杂度,比 O(n³) 的矩阵树定理快了几个数量级 —— 这正是"看出仙人掌结构"带来的全部红利。
// 「无向图迭代 DFS + 回边找基本环」通用骨架 for (int s = 1; s <= n; s++) { if (vis[s]) continue; vis[s] = true; dep[s] = 0; // 根深度为 0 int top = 0; stNode[top] = s; stPar[top] = 0; stIt[top] = head[s]; top++; while (top > 0) { int u = stNode[top - 1]; if (stIt[top - 1] == 0) { top--; continue; } // 边扫完,回溯 int e = stIt[top - 1]; stIt[top - 1] = nxt[e]; int w = to[e], p = stPar[top - 1]; if (w == p) continue; // 不走父边 if (vis[w]) { if (dep[w] < dep[u]) { // 回边:一个环只算一次 int cycleLen = dep[u] - dep[w] + 1; // 基本环长度 // 仙人掌:ans = ans * cycleLen % MOD; // 一般图:还需要去重(环可能共享边) } } else { vis[w] = true; dep[w] = dep[u] + 1; stNode[top] = w; stPar[top] = u; stIt[top] = head[w]; top++; } } } // 生成树计数的两条路 // (1) 仙人掌:答案 = Π 每个简单环的长度 O(n + m) // (2) 一般图:基尔霍夫矩阵树定理(行列式) O(n³)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 迭代 DFS | 用 depth 判定回边、求基本环长度 | 仙人掌、点双 / 边双、环上计数类问题 |
| 父边跳过 | 无向边存两遍,必须排除回去的那条 | 所有"无向图上的 DFS 遍历" |
| 独立事件相乘 | 桥必留 × 每环断一条 = Π 环长 | 各类"结构可分解,各部分方案数独立"的计数题 |
| 手写栈 | n = 10⁵ 时避免递归爆栈 | 所有深度可能达到 10⁵ 的图 / 树遍历 |
c 条并列最大边,则该环有 c 种选择,最后仍然相乘。把"断哪条都行"升级成"只能断最贵的(并列则都行)",是这类"环上选择"问题的标准改法。)