连通分量
无向图的连通分量是一组能沿路径互相到达的顶点，并且无法再加入其他顶点。一轮 DFS 或 BFS 只能找到起点所在的分量。要数清全部分量，还需从头扫描所有顶点，在每个未访问顶点启动一次填充。总时间为 O(V + E)，启动次数就是分量数。
外层循环会跳过很多顶点，这不是多余工作：它们已经由先前的填充归入某个分量。扫描到尚未着色的顶点，才说明遇到了新分量。若只从 0 搜索一次，就会漏掉其余区域。
为什么需要外层扫描
外层用 for start in range(n) 逐个检查顶点。已有颜色就跳过；没有颜色就创建新分量，从该点填充全部可达顶点，再继续扫描。
本课的填充采用显式栈实现 DFS，并在入栈时着色。先压入并标记起点，然后反复出栈，给尚未着色的邻居标上当前分量颜色并入栈，直到栈空。
无向图的可达性对称：若能从 a 到 b，也能返回。因此从一个分量中的任意顶点开始，都能填满整个分量。换成队列做 BFS，内部着色顺序会改变，分量划分不会变；划分由图决定。
这种方法适合静态无向图中的网络分组、网格岛屿和相关项。若边不断加入，Union-Find 可以增量维护同一划分。若要求有向图中顶点互相可达，则要计算强连通分量，例如使用两遍扫描的 Kosaraju 或一遍 DFS 的 Tarjan，不能直接套用这里的填充。
连通分量逐步演示
默认图有八个顶点：三角形 {0, 1, 2} 的边为 0–1、1–2、2–0；顶点对 {3, 4} 之间有边 3–4；链 {5, 6, 7} 的边为 5–6、6–7。外层按 0 到 7 扫描。
- 到达未着色的 0，创建分量 #1。标记并压入 0；弹出后标记、压入 1 和 2。先弹出 2，再弹出 1，它们的邻居都已归入 #1，栈清空，得到
{0, 1, 2}。 - 到达 1，已在 #1，跳过。
- 到达 2，已在 #1，跳过。它们在外层扫描到来前就由填充完成了归属。
- 到达未着色的 3，创建 #2。压入 3，弹出后标记并压入 4；弹出 4 时邻居 3 已着色。栈空，得到
{3, 4}。 - 到达 4，已在 #2，跳过。
- 到达未着色的 5，创建 #3。依次从 5 填充到 6、7。7 的邻居 6 已着色，栈空，得到
{5, 6, 7}。 - 到达 6，已在 #3，跳过。
- 到达 7，已在 #3，跳过，扫描结束。
结果为 3 个分量。外层迭代 8 次，启动填充 3 次，跳过 5 次。每个顶点在外层扫描时，要么成为新分量起点，要么已经着色而被跳过，两种情况互斥且覆盖全部顶点。
一个连通图预设只启动一次填充，其余迭代都跳过。分散预设包含孤立顶点：即使没有边，也会单独启动填充。全部孤立预设把这一点推到极限，没有任何边，启动 n 次填充，跳过零次。
时间与空间复杂度
| 情况 | 时间 | 空间 |
|---|---|---|
| 全图 | O(V + E) | O(V) |
外层检查 V 个顶点。所有填充合计，每个顶点入栈、出栈各一次，每条无向边从两个端点各检查一次，因此不是每个分量各付一次全图成本，总量为 O(V + E)。
访问颜色和栈占 O(V) 空间。栈最坏可保存 O(V) 个待处理顶点，例如弹出星形图中心后，其余顶点同时入栈。这里的显式栈在长链上不一定很大，不能和递归调用栈混为一谈。
边界情况
- 单个顶点构成一个分量，填充没有邻居便结束。
- 孤立顶点没有边，仍是大小为一的分量，外层必须检查它。
- 所有顶点连通时，启动一次填充，其余全部跳过。
- 全部顶点孤立时，有
n个分量，是最大数量，每个顶点都启动填充。
常见错误
- 只运行一次 DFS/BFS。它只能找出起点所在分量，必须在外层重启搜索。
- 忽略无边顶点，导致数量和划分都不正确。
- 出栈时才标记。同一顶点可能在首次出栈前被多次压入，增大栈，某些写法还会算错数量。本实现入栈就标记。
- 混淆连通分量和强连通分量。有向边不保证相互可达，需要 Kosaraju、Tarjan 等 SCC 算法。
- 认为 DFS 和 BFS 得到不同分量。它们改变探索顺序，不改变无向图的连通划分。