什么是连通分量和强连通分量？怎么求？

简化版

连通分量（无向图）：图里一个个「互相能到达」的极大顶点群。求法：对每个没访问过的点做一次 DFS/BFS，一次遍历标记一个分量，或用并查集。强连通分量 SCC（有向图）：一个顶点群里任意两点都能互相到达（双向）。求法：Tarjan（一次 DFS + dfn/low 数组）或 Kosaraju（正反图各一次 DFS），都是 O(V+E)。

详细版

无向图：连通分量

「连通」= 无向图里两点有路径可达。连通分量是极大的连通子图。求所有连通分量：

int count = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        dfs(i, visited, adj);  // 一次 DFS 走完一个连通分量
        count++;               // 分量数 +1
    }
}
// count 就是连通分量个数

用并查集也行：合并所有边的两端，最后不同的根的个数 = 连通分量数。

有向图：强连通分量（SCC）

有向图里，「强连通」要求双向可达（u 能到 v 且 v 能到 u）。强连通分量是极大的强连通子图。求法：

Tarjan 算法：一次 DFS，维护 dfn[]（访问时间戳）和 low[]（能回溯到的最早祖先），配合一个栈，当 dfn[u] == low[u] 时弹出一个 SCC。O(V+E)。
Kosaraju 算法：① 对原图 DFS，记录完成顺序；② 对反图按完成顺序的逆序再 DFS，每棵 DFS 树是一个 SCC。两次 DFS，O(V+E)。

完整版教学

一、连通 vs 强连通：方向的差别

这是本题的关键区分。

无向图只有「连通」：两点之间有路径就行（无向路径天然双向）。
有向图要区分「弱连通」和「强连通」：强连通要求 u→v 和 v→u 都有有向路径（互相可达）。因为有向边单行，A 能到 B 不代表 B 能回 A。

所以无向图求「连通分量」简单（一次遍历一个），有向图求「强连通分量」难（要保证双向可达），需要专门的 Tarjan/Kosaraju 算法。

二、无向图连通分量：遍历即可

无向图求连通分量非常直接：对每个未访问的点启动一次 DFS/BFS，一次遍历就能访问完它所在的整个连通分量，分量计数加一。遍历完所有点，计数就是连通分量数。或者用并查集：把每条边的两端合并，最后统计有多少个不同的根。两种方法都是 O(V+E)。

三、有向图为什么需要专门算法

有向图不能像无向图那样「一次 DFS 一个分量」——因为从某个点 DFS 能到达的点，未必能回到它（不是强连通）。需要更精巧的办法来识别「互相可达的极大群」。核心思路是找到每个 SCC 的「入口/根」，把属于同一个 SCC 的点归到一起。

四、Kosaraju：两次 DFS 的直觉

Kosaraju 的巧妙在利用反图：

第一次对原图 DFS，记录每个点的完成时间（后序）。
把所有边反向（得到反图）。
按第一次完成时间的逆序，对反图做 DFS。每一棵 DFS 生成树里的点，就是一个强连通分量。

为什么对？因为在原图和反图里都能互相到达的点，才是真正的 SCC。用完成时间的逆序保证了「从每个 SCC 的『最晚完成的代表』开始」，反图 DFS 就只能走到同一个 SCC 内部。

五、Tarjan：一次 DFS 更高效

Tarjan 只需一次 DFS，用两个数组：

dfn[u]：u 被首次访问的时间戳。
low[u]：u 通过子树和后向边能到达的最小 dfn。

DFS 时维护一个栈存「当前路径上的点」。当 dfn[u] == low[u] 时，说明 u 是某个 SCC 的根，从栈里弹出直到 u 为止的所有点构成一个 SCC。一次遍历搞定，常数更小，是竞赛/工程更常用的 SCC 算法。

六、常见误区与追问

考点	正确口径
连通分量	无向图中互相可达的最大点集
强连通分量	有向图中任意两点互相可达的最大点集
常用算法	无向图 DFS/BFS，有向图 Tarjan/Kosaraju

undirected components:
for v in vertices:
  if not visited[v]:
    dfs(v)
    count++

有向图的“能到达”不等于“互相能到达”，这就是 SCC 比连通分量更难的原因。

误区：有向图只要忽略方向做 DFS 就能得到强连通分量。 忽略方向得到的是弱连通关系，不能保证任意两点互相可达。
误区：连通分量必须两两有直接边。 只要路径可达即可，不要求任意两点之间直接相连。
误区：遍历一次只能找到一个分量所以复杂度很高。 所有 DFS/BFS 总共访问每个点和边一次，整体 O(V+E)。
追问：Kosaraju 为什么要反图？ 第一次 DFS 得到完成时间顺序，反图上按该顺序能分离出源/汇 SCC。
追问：Tarjan 的 lowlink 表示什么？ 表示当前节点通过 DFS 树边和返祖边能追溯到的最早节点编号。
追问：并查集能求什么？ 适合无向图连通分量动态合并，不适合直接求有向强连通分量。

七、加强记忆

连通分量（无向图）：互相可达的极大点群，对每个未访问点 DFS/BFS 一次得一个分量，或用并查集（不同根数）。强连通分量 SCC（有向图）：任意两点双向可达（有向要 u↔v 都通）——用 Tarjan（一次 DFS + dfn/low + 栈，dfn==low 时出栈一个 SCC）或 Kosaraju（原图 DFS 记完成序 + 反图逆序 DFS），都 O(V+E)。核心区别：无向只需可达、有向需双向可达。应用:社群发现、缩点。

简化版

详细版