GESP 题解库 / 8 级题解 / [GESP202609 八级] 生成树计数 · 第 23 / 24 题
GESP202609 八级 · P17461 · 困难

仙人掌生成树计数

桥必须保留,每个简单环恰好断掉一条边 —— 答案就是所有环长的乘积。

🌵
n, m ≤ 10⁵
仙人掌图的规模
🔁
每条边至多属于一个简单环
题目给的特殊性质
⚡
O(n + m)
一次迭代 DFS
🎯
Π 每个环的长度
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

(GESP202609 八级)给定一张有 n 个顶点 m 条边的无向连通图 G,顶点依次以 1, 2, … , n 编号。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⁵
💡
人话翻译:"每条边至多属于一个简单环"这个条件,专业名字叫仙人掌图(cactus)——把图想象成"若干个环用桥串起来",环与环之间最多只共享一个顶点,绝不会有一条边同时被两个环用。
仙人掌的生成树有个极其干净的结论:桥必须全部留下,而每个简单环必须恰好断掉一条边。
断掉环上的哪一条都行,一个长度为 k 的环就贡献 k 种选择;各环互不干扰,所以总方案数 = 所有环长的乘积。
所以这道题变成了:"找出所有简单环的长度,乘起来"。

🔍 关键词提取

仙人掌图生成树计数桥必留 + 每环断一条答案 = Π 环长DFS 回边判环迭代写法防爆栈取模 998244353

已知条件

项目说明
输入第一行 n, m;随后 m 行每行 uᵢ, vᵢ 表示一条无向边
输出生成树数量对 998244353 取模
图的性质连通、无向、无重边、无自环
关键限制每条边至多属于一个简单环(仙人掌)
数据范围1 ≤ n, m ≤ 10⁵
部分分40% 保证 n ≤ 8;60% 保证 n ≤ 2000

需要解决的问题

02
思维导图
整理解题思路的全貌
🌵 桥必留、每环断一条 → Π 环长
🧠 核心结论
桥必须全部保留(无自由度)
每个简单环恰好断掉一条边
长度为 k 的环贡献 k 种选择
答案 = Π 每个环的长度
🔍 怎么找环
无向图 DFS + 记录深度
回边 (u, w):w 是 u 的祖先
环长 = depth[u] − depth[w] + 1
仙人掌中基本环两两边不相交
🛠️ 实现要点
邻接表存无向图(双向加边)
手写栈迭代 DFS,防爆栈
用父结点跳过父边
每乘一次都对 998244353 取模
⚠️ 易错点
递归 DFS 在长链上爆栈
重复统计同一个环(需要深度判断)
n = 1, m = 0 时答案是 1(空乘积)
乘法忘记开 long long
03
样例手算推导
样例 1(两个环 → 3 × 4 = 12)与样例 2(树 → 1)的完整推演

🧮 样例 1:两个环,3 × 4 = 12

样例 1 长这样:

7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4

期望输出 12。我们先把图拆开看:

组成部分边类型环长 / 是否必留
环 A1–2, 2–3, 3–1长度为 3 的简单环环长 3 → 3 种断法
桥3–4桥必须留在生成树里
环 B4–5, 5–6, 6–7, 7–4长度为 4 的简单环环长 4 → 4 种断法
1
第 1 步:把桥钉死

图上一共 7 个顶点,生成树需要 7 − 1 = 6 条边

边 3–4 是桥:删掉它,{1,2,3} 与 {4,5,6,7} 就断开了

所以 3–4 必须选,占掉 1 个名额

✅ 桥 3–4 一定在树里

2
第 2 步:环 A 断一条

环 A 有 3 条边:1–2、2–3、3–1

若三条全留,就形成回路 → 不是树

断掉任意一条,环被拉直,剩下 2 条边把 1、2、3 连成一棵树

可选的断法有 3 条 → 3 种方案

✅ 环 A 贡献 3

3
第 3 步:环 B 断一条

环 B 有 4 条边:4–5、5–6、6–7、7–4

同理必须且只需断一条,可选断法有 4 条

环 A 与环 B 不共享任何一条边(只通过桥 3–4 相连)

所以两者的选择互相独立

✅ 环 B 贡献 4

4
第 4 步:乘法原理

总方案数 = 3 × 4 = 12

边数校验:桥 1 条 + 环 A 留 2 条 + 环 B 留 3 条 = 6 条 = n − 1 ✓

顶点数校验:7 个顶点、6 条边且连通无环 → 确实是生成树 ✓

✅ 答案 12

3 × 4 = 12 ✓

用 DFS 找出这两个环

DFS 顺序回边 (u, w)depth[u]depth[w]环长 = depth[u] − depth[w] + 1
1 → 2 → 33 → 1202 − 0 + 1 = 3
3 → 4 → 5 → 6 → 77 → 4525 − 2 + 1 = 4
🔑
回边的判定要点:无向图 DFS 里,每条非树边都连接"某个点"和"它的祖先"。
判据是 depth[w] < depth[u]:被访问过且深度更小,说明 w 在 u 的上方,这是一条回边;反过来 depth[w] > depth[u] 的那些,是同一个环从另一头被看到,必须跳过,否则同一个环会被算两次。

🧮 样例 2(树)+ 两个必须想明白的问题

样例 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

问题一:为什么基本环两两边不相交?

1
先看仙人掌的定义

题目说"每条边至多属于一个简单环"

也就是说:任何一条边,不可能同时被两个不同的简单环用到

两个环最多只能共享一个顶点(像两个圆相切的切点)

这正是"仙人掌"这个名字的由来

✅ 环与环的边集合互不相交

2
再看 DFS 基本环

无向图 DFS 中,每条回边 (u, w) 与"树上从 w 到 u 的路径"

合起来构成一个基本环

不同回边对应的基本环,树边部分天然不重叠

(否则某条树边就会落在两个基本环里,与仙人掌性质矛盾)

✅ 基本环 = 全部简单环,两两不交

3
所以可以放心直接相乘

一般图上"回边个数"远多于"简单环个数",需要去重

但仙人掌上,回边与简单环一一对应

所以 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。
04
解法对比
DFS 求环长乘积 vs 矩阵树定理 vs 暴力枚举边子集

⚔️ 解法对比

🟢 迭代 DFS 找环 + 环长相乘 推荐

一次 DFS,遇到回边就乘上 (depth[u] − depth[w] + 1),最后取模

  • 时间 O(n + m)
  • 空间 O(n + m)
  • 代码约 45 行
  • 完全利用仙人掌性质,最优
💡
正确性链条:仙人掌里"桥必留 + 每环恰好断一条"两者互相独立,于是答案就是 Π 环长;而 DFS 的回边与简单环一一对应,所以数回边 = 数环。两个观察咬合上,一行乘法就结束了。

🟠 基尔霍夫矩阵树定理

构造拉普拉斯矩阵,删掉一行一列后求行列式

  • 时间 O(n³)(高斯消元)
  • 对任意图都成立
  • n ≤ 2000 时才能勉强跑
  • n = 10⁵ 时完全不可行
⚠️
它的价值:如果你没看出"仙人掌"这个性质,矩阵树定理是"万能"的,可惜 10⁵ 的行列式根本算不动,只能拿 60 分的部分分。

📈 性能对比

方案复杂度结论
迭代 DFS + Π 环长O(n + m)✅ 正解,能拿满分
矩阵树定理(高斯消元)O(n³)⚠️ 只对 n ≤ 2000 的部分分有效
枚举所有 n − 1 条边子集C(m, n−1),指数级❌ 40 分暴力专用
05
算法流程图
迭代 DFS + 回边判环:主流程
开始读入 n, m 与 m 条无向边,建邻接表ans = 1;vis[] 与 depth[] 全部清零取一个未访问顶点 s 入栈,vis[s] = 1,depth[s] = 0栈空了吗?没空 ✓取栈顶继续扫边空了 ✗换下一个起点这条边的另一端是父结点吗?是 ✓跳过这条父边否 ✗继续判断另一端 w 已经被访问过吗?访问过 ✓判深度没访问 ✗压栈继续 DFS若 depth[w] < depth[u]:ans = ans × (depth[u] − depth[w] + 1) % 998244353所有顶点都访问过了吗?输出 ans(所有环长的乘积 mod 998244353)继续 DFS
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌵 环长乘积计算器(生成树计数)

第一行输入 n 与 m,随后 m 行每行一条无向边 u v(保证是仙人掌)。程序用迭代 DFS 找出所有基本环并相乘。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(迭代 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迭代 DFSn = 10⁵ 的长链会让递归爆栈,必须迭代
⚠️
五个坑:① 用递归 DFS,长链上栈溢出(n = 10⁵ 时必 RE);② 忘记判断 dep[w] < dep[u],同一个环被乘两次(答案平方);③ ans 初值写成 0,无环时输出 0 而不是 1;④ 乘法不开 long long(ans 可达 10⁹、环长可达 10⁵,乘积约 10¹⁴,int 溢出);⑤ 邻接表只加单向边,导致 DFS 遍历不到整个图。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
12题面样例 1:环长 3 与 4,3 × 4 = 12
5 4
1 2
1 3
2 4
2 5
1题面样例 2:无环(树),空乘积 = 1
3 3
1 2
2 3
3 1
3单个三角形:环长 3 → 3
4 4
1 2
2 3
3 4
4 1
4单个 4-环:环长 4 → 4
5 6
1 2
2 3
3 1
1 4
4 5
5 1
9两个 3-环共享顶点 1:3 × 3 = 9
4 3
1 2
2 3
3 4
1一条链(全是桥):唯一生成树
1 01只有一个顶点:唯一的空树,答案 1
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 8
8 4
153-环与 5-环用桥相连:3 × 5 = 15
✅
自查清单:① 是迭代 DFS 吗?② 判了 dep[w] < dep[u] 吗?③ ans 初值是 1 吗?④ 每一步都取模了吗?

🚨 易错点清单

⚠️
递归 DFS 爆栈:n = 10⁵ 的长链会让递归深度到 10⁵,务必改写成手写栈的迭代版本。
⚠️
同一个环被算两次:只写 if (vis[w]) 就乘,会把环从两头各看一次,必须加上 dep[w] < dep[u]。
⚠️
ans 初值错了:写成 0 会让"无环"的图输出 0,而正确答案是 1(空乘积为 1)。
⚠️
乘法溢出:ans 与环长相乘可达约 10¹⁴,必须用 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + m)
空间复杂度
O(n + m)
DFS 方式
迭代(手写栈)
模数
998244353

时间怎么算的?

空间都用在哪?

邻接表用"链式前向星"存 2m 条有向边,配 head / nxt / to 三个长度为 2m + 1 的数组;另外还有 dep、vis 与长度 n 的手写栈,总空间 O(n + m)。

✅ 线性复杂度,比 O(n³) 的矩阵树定理快了几个数量级 —— 这正是"看出仙人掌结构"带来的全部红利。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「无向图迭代 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⁵ 的图 / 树遍历
🌟
思考题:如果题目改成"仙人掌图的最小生成树数量"(每条边带不同的边权),"Π 环长"还能直接用吗?(提示:不能。有了边权之后,每个环只能断掉"环上权最大的那条边",除非出现并列最大——所以答案要对每个环分别处理:若环上唯一最大边只有一条,该环只剩 1 种选择;若有 c 条并列最大边,则该环有 c 种选择,最后仍然相乘。把"断哪条都行"升级成"只能断最贵的(并列则都行)",是这类"环上选择"问题的标准改法。)