用 Tarjan 算法求解有向图的强连通分量
图论中的连通性概念是许多算法与应用的基础。当我们研究网络结构、依赖关系或路径问题时，理解图中的连通性质至关重要。对于不同类型的图，连通性有着不同的表现形式和算法解决方案。无向图与有向图的连通性
在无向图中，连通分量是指图中任意两个顶点之间都存在路径的最大子图。寻找无向图的连通分量相对简单，通过一次深度优先搜索(DFS)或广度优先搜索(BFS)就能识别所有连通分量。
然而，在有向图中，情况变得复杂得多。因为有向图中的边具有方向性，从顶点 A 能到达顶点 B，并不意味着从 B 也能到达 A。这就引出了强连通分量(Strongly Connected Component, SCC)的概念：在有向图中，如果一个子图内的任意两个顶点 u 和 v 都满足 u 可以到达 v 且 v 也可以到达 u，那么这个子图就是强连通的。“极大”要求，每个图都可以划分成多个强连通分量。的强连通子图，就是一个强连通分量，由于有了“极大”要求，每个图都可以划分成多个强连通分量。
强连通分量的重要性
强连通分量分析在许多领域都有重要应用：
[*]编译器优化：识别代码中的循环依赖，优化执行顺序
[*]社交网络分析：发现紧密互动的用户群体
[*]电子电路设计：分析信号传播路径
[*]生态系统建模：研究物种间的相互依赖关系
Tarjan算法的地位
在众多求解强连通分量的算法中，Robert Tarjan于1972年提出的Tarjan算法因其高效性和优雅性而广受推崇。与Kosaraju算法相比，Tarjan算法具有以下优势：
[*]单次DFS遍历：只需一次深度优先搜索即可完成
[*]线性时间复杂度：O(V+E)的时间复杂度，其中V是顶点数，E是边数
[*]空间效率：仅需维护几个辅助数组和栈
Tarjan 算法的原理到实现
Tarjan 算法通过一次 DFS 来划分出所有的强连通分量，在搜索中，需要维护几个关键数组和数据结构来追踪图中节点的状态：
[*]发现时间数组(disc)：记录每个节点在DFS遍历中被首次访问的时间戳。这个时间戳单调递增，为每个节点提供唯一的访问序号。
[*]最低访问数组(low)：存储每个节点通过树边和后向边能够回溯到的最早访问节点的发现时间。这是识别SCC的核心依据。
[*]栈状态标记(onStack)：布尔数组，指示节点当前是否在算法使用的辅助栈中。这帮助我们区分有效的后向边。
[*]栈(stk)：按照DFS访问顺序存储节点，用于在发现完整SCC时提取相关节点。
这些数据结构共同协作，使得我们能够在单次DFS遍历中完成SCC识别。初始化时，disc和low数组设为0，onStack设为false，栈为空。
用深度遍历遍历求解强连通分量
算法的核心在于精心设计的DFS遍历，它不仅仅进行简单的图遍历，还通过维护上述数据结构来识别SCC：
void dfs(int u) {
// 设置发现时间和初始low值
disc = low = ++time;
stk.push(u);
onStack = true;
// 遍历所有邻接节点
for (int v : edges) {
if (!disc) { // 未访问的节点（树边情况）
dfs(v);
low = min(low, low);
}
else if (onStack) { // 已访问但在栈中（后向边情况）
low = min(low, disc);
}
}
// 检查是否是SCC的根节点
if (low == disc) {
vector<int> scc;
while (true) {
int v = stk.top();
stk.pop();
onStack = false;
scc.push_back(v);
if (v == u) break;
}
sccs.push_back(scc);
}
}节点首次访问
当DFS首次访问一个节点u时，算法执行以下关键操作：
disc = low = ++time;
stk.push(u);
onStack = true;按照定义 disc记录的是节点的"发现时间"，这个时间戳随着遍历严格单调递增（每个节点获得唯一序号），反映DFS遍历的拓扑顺序。
初始时low设为与disc相同，表示目前只知道 u 能到达自身，稍后随着搜索进行，low可能会降低。
入栈操作将 u 本身放入，并以onStack标记，并把似乎是调用栈的副本。但是在函数结束后并没有被弹出，他们会在回溯到if (low == disc)时被统一弹出。
DFS 递归调用
if (!disc) {
dfs(v);
low = min(low, low);
}若下一个节点从未访问过，则正常访问，并按照定义更新low。这个过程如同节点在问："我的子节点能连接到多早的祖先？"
else if (onStack) {
low = min(low, disc);
}若下一个节点已经访问过，且仍在大栈内呢？那么这条边叫做后向边，是指向DFS栈中活跃节点的边，它揭示了潜在的环路：
使用disc而非low来更新。因为我们需要记录的是"直接"通过这条后向边能到达的最早节点
[*]使用low可能导致跨SCC的信息污染（如图中存在多个SCC时）
[*]onStack检查确保我们只考虑当前DFS路径上的节点（灰色节点），忽略已经处理完的SCC（黑色节点）
若下一个节点已经访问过，且不在大栈内呢？那么这条边叫做横叉边（cross edge），是指连接不同子树的边。算法中我们故意忽略不在栈中的已访问节点，这是因为忽略不在栈中的已访问节点不会影响SCC识别，不在栈内的这些节点属于已经划分处理的SCC。
实例说明：
考虑图A→B→C→A：
[*]当处理边C→A时，发现A在栈中
[*]于是更新low = min(low, disc)
[*]这个信息会通过递归返回传播到B和A
[*]最终A的low等于disc，识别出SCC
（注：示意图中 2，3，4 所在强连通分量标注有误，应该是3→4或双向边）
SCC识别的过程
SCC识别的核心代码段：
if (low == disc) {
vector<int> scc;
while (true) {
int v = stk.top();
stk.pop();
onStack = false;
scc.push_back(v);
if (v == u) break;
}
sccs.push_back(scc);
}为什么这个条件能识别SCC根？
[*]low == disc表明u无法回溯到更早的节点
[*]从u出发的所有路径最终都只能回到u或其后代
[*]栈中u上方的节点都满足：
[*]是u在DFS树中的后代
[*]都能通过某种路径回到u（否则它们的low值会使u的low值变小）
栈结构的精妙设计：
[*]栈维护了当前DFS路径的所有活跃节点
[*]节点出栈顺序保证了SCC的完整性：
[*]后进先出的特性确保总是先处理完所有后代
[*]当遇到SCC根时，其所有后代都位于栈顶连续位置
此时，u 和其上方所有节点出栈，他们构成一个强连通分量。
Tarjan 搜索树的性质
下面这些性质可以帮助你更好的理解算法的工作原理。
SCC 形成子树的证明
引理1：在DFS树中，一个SCC的所有节点形成一棵连通的子树。
证明：
[*]设SCC的根节点为r（disc最小）
[*]对SCC中任意节点u，存在路径u→r和r→u
[*]由于r最早被发现，路径r→u必须全部由u的祖先组成
[*]因此u必须是r的后代
推论：SCC识别可以限制在DFS树的单个子树范围内。
low值传播的正确性
定理1：low正确计算了u能回溯到的最早祖先。
归纳证明：
[*]基例：叶子节点的low值正确（只能通过后向边更新）
[*]归纳步骤：假设所有子节点的low值正确
[*]树边传播：low = min(low, low)
[*]后向边更新：low = min(low, disc)
[*]这两种更新覆盖了所有可能的回溯路径
栈维护的完整性
引理2：当low == disc时，栈中u上方的节点恰好构成以u为根的SCC。
证明：
[*]这些节点都是u的后代（由DFS栈的性质保证）
[*]每个节点v都能到达u：
[*]因为low没有被这些节点减小
[*]即不存在从这些节点到u的祖先的路径
[*]u能到达所有这些节点（因为是它们的祖先）
[*]极大性由栈的弹出操作保证
总的来说，在有多个SCC的图中，算法的正确性依赖于：
[*]隔离性：不同SCC的处理互不干扰
[*]顺序性：SCC按照拓扑逆序被识别（最深的SCC最先被处理）
[*]完备性：每个节点最终都会被某个SCC包含
这种隔离处理的能力使得算法能够高效处理大规模复杂图结构。
class Graph { vector edges; int n; int time = 0; vector disc, low; vector onStack; stack stk; vector sccs; void dfs(int u) { // ... }public: Graph(int n) : n(n), edges(n), disc(n), low(n), onStack(n) {} void addEdge(int u, int v) { edges.push_back(v); } vector findSCCs() { for (int i = 0; i < n; ++i) { if (!disc) dfs(i); } return sccs; } void printSCCs() const { for (const auto& scc : sccs) { cout
页:
[1]