题目来源：参考 LeetCode 323：无向图中连通分量的数目进行课程化改编。原题只返回分量数量；本 Lab 使用标准输入输出，并额外输出每个顶点的分量编号。
学习目标
前置知识
完成前建议先阅读第 7.1 节 图的遍历：DFS 与 BFS的"DFS 能做什么"小节。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。
题目
给定一个含 n 个顶点和 m 条边的无向图。如果两个顶点之间存在路径，它们就属于同一个连通分量。请统计连通分量总数，并按下述固定规则为每个顶点标注所属分量；孤立顶点没有相邻边，也单独构成一个连通分量。
输入格式
第一行包含两个整数 n m，分别表示顶点数和无向边数。顶点编号为 0 到 n-1。
接下来 m 行，每行包含两个整数 u v，表示一条无向边。输入保证：
1 <= n <= 10000；0 <= m <= 100000；0 <= u, v < n；- 不包含自环和重复边；
- 图不保证连通。
遍历使用 DFS：按编号从 0 到 n-1 扫描，对尚未标记的顶点启动 DFS，并把该顶点所在连通分量的所有顶点标记为同一个编号。分量编号只由外层扫描发现新分量的顺序决定，与分量内部的邻居访问顺序无关，因此无需排序邻接表。
输出格式
输出两行：
- 第一行包含一个整数
k：连通分量的个数； - 第二行包含
n个整数：comp[0] comp[1] ... comp[n-1]，其中comp[u]是顶点u所属分量的编号。
分量编号按发现顺序从 0 开始递增：扫描时第一个启动 DFS 的顶点所在分量编号为 0，第二个为 1，依此类推。相邻整数之间用单个空格隔开，行末无空格。
样例输入
6 2
0 1
2 3样例输出
4
0 0 1 1 2 3任务
- 读入无向图并构建邻接表；
- 按
0..n-1扫描，遇到未标记顶点时启动 DFS，把所有可达顶点标记为当前分量编号； - 每启动一次 DFS 分量编号加一，统计总个数；
- 输出分量个数与分量编号数组。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 一般非连通图 | 每个连通分量恰好一次 DFS，编号按发现顺序递增 |
| 连通图 | k = 1，所有顶点分量编号为 0 |
| 全部孤立点 | 每个顶点一个分量，k = n，编号 0..n-1 |
| 单顶点图 | k = 1，comp[0] = 0 |
| 链状/星形图 | 一个分量，k = 1 |
| 含环图 | 环上顶点同属一个分量，不重复计数 |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-02-connected-components
pnpm lab:run -- labs/chapter-07/exercise/E-07-02-connected-components
pnpm lab:score -- labs/chapter-07/exercise/E-07-02-connected-components完成清单
复杂度分析
每个顶点恰好进入一次；邻接表中的每条记录扫描一次，也就是每条无向边分别从两个方向扫描，总时间为 O(n + m)。邻接表与 comp 数组共占 O(n + m) 空间。递归栈最坏深度为 O(n)，实际可用深度取决于系统与编译器；需要处理更深图时应改用显式栈。
思考与复盘
- 为什么只从
0出发跑一次 DFS 会漏掉其他分量？如何补全？
查看参考答案
一次 DFS 只能覆盖从 0 可达的分量。应按 0..n-1 扫描，遇到未标记顶点就启动新的 DFS，并标记为新的分量编号。
- 若把 DFS 换成 BFS，在本题的扫描规则下，分量编号会变吗？为什么？
查看参考答案
不会。外层扫描顺序决定新分量编号，DFS/BFS 都会遍历该起点可达的全部顶点；只有分量内部访问顺序可能不同。
- 有向图中应明确讨论“弱连通分量”还是“强连通分量”；两者各自采用什么可达标准？
查看参考答案
弱连通分量忽略方向判断连通；强连通分量要求任意两点彼此可达。普通无向 DFS 只能直接求弱连通意义的分量，强连通分量应使用 Tarjan 或 Kosaraju。