C++如何实现图的强连通分量分解（Tarjan算法）-C++-PHP中文网

因为low[u]必须表示u能通过树边加至多一条非树边到达的最小dfn值，而非仅用disc[u]替代；只有v在栈中时才可用dfn[v]更新low[u]，否则会错误提前弹出节点导致scc划分错误。

c++如何实现图的强连通分量分解（tarjan算法）

为什么 Tarjan 的 `lowlink` 不能直接用 `disc` 替代

很多人写完 Tarjan 发现结果错，根源常出在 lowlink[u] 的更新逻辑上。它必须表示「u 能通过若干条树边 + 最多一条后向边/横叉边到达的最小发现时间」，而不是当前节点的发现时间 disc[u]。如果误写成 low[u] = min(low[u], disc[v])（漏掉对栈中节点的判断），就会把非强连通分支内的节点提前弹出。

关键约束：只有当 v 在栈中（即 inStack[v] == true）时，才允许用 disc[v] 更新 low[u]；否则说明 v 所属 SCC 已确定，不应影响当前分支的连通性边界。

常见错误现象：vector<vector>></vector> 返回的 SCC 数量偏多、单个 SCC 内节点数偏少、甚至出现空 SCC。

如何正确维护栈和 `inStack` 数组

Tarjan 不是 DFS 遍历完就结束，它依赖一个显式栈来暂存当前 DFS 树路径上的活跃节点。每次进入新节点 u，必须：

将 u 压入栈，并设 inStack[u] = true
DFS 返回后，若 low[u] == disc[u]，说明找到了一个 SCC 根——此时要持续弹栈直到弹出 u 自身
弹出过程中每个节点都属于同一个 SCC，且必须立即标记 inStack[v] = false

漏掉 inStack 的置 false 操作，会导致后续节点错误地认为已出栈节点仍在当前 SCC 路径上，从而污染 low 更新；不检查 inStack[v] 就更新 low，等价于把已闭合的 SCC 当作可回溯路径。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

`std::stack` 还是 `vector` 模拟栈？性能与调试差异

两者语义一致，但 vector 更利于调试：

用 vec.back() 和 vec.pop_back() 模拟栈顶操作，可在调试时直接打印 vec 观察栈状态
std::stack 默认基于 deque，不支持遍历，出问题时难以确认栈内是否残留不该存在的节点
性能无实质差异：Tarjan 时间复杂度为 O(V + E)，栈操作是常数级开销

示例片段（使用 vector）：

vector<int> stack;
vector<bool> inStack(n, false);
// ...
stack.push_back(u);
inStack[u] = true;
// ...
while (stack.back() != u) {
    int v = stack.back(); stack.pop_back();
    inStack[v] = false;
    component.back().push_back(v);
}
int v = stack.back(); stack.pop_back();
inStack[v] = false;
component.back().push_back(v);
</bool></int>

有向图输入含重边或自环时怎么处理

Tarjan 算法本身对重边和自环天然鲁棒，但实现时需注意：

自环 u → u：在 DFS 中访问自身，此时 v == u 且 inStack[u] == true，会触发 low[u] = min(low[u], disc[u])，不影响逻辑，但建议在建图时过滤（避免冗余迭代）
重边：多次访问同一对 (u, v)，若不判重，可能重复更新 low[u]，浪费计算；可用 visited_edge[u][v] 或邻接表去重预处理
更稳妥做法：构建邻接表时用 set<vector>></vector> 或排序+去重，尤其当输入边来自文件或网络时