C++无向图桥的判定怎么通过强连通Tarjan low值判断-C++-PHP中文网

不能直接用强连通tarjan的low值判断无向图的桥，因其low定义依赖有向图的后向边方向性，而无向图需过滤父子边（i!=(fa^1)）并单独处理重边，否则会导致桥全部漏判。

c++无向图桥的判定怎么通过强连通tarjan low值判断

不能直接用强连通 Tarjan 的 low 值判断无向图的桥——因为强连通 Tarjan 是为有向图设计的，而无向图的桥判定依赖另一套逻辑，核心条件是 low[v] > dfn[u]，且必须配合无向图专用的边去重处理。

为什么强连通 Tarjan 的 low 定义不适用于无向图桥判定

强连通 Tarjan 中的 low[u] 定义为“u 或其子孙能通过一条后向边到达的最小 dfn 值”，这个定义隐含了方向性：后向边只允许从后代指向祖先（即栈内已访问节点）。但无向图中每条边 (u,v) 被拆成两条有向边 u→v 和 v→u，若不加区分，v→u 会被误认为“后向边”而错误更新 low[u]，导致 low[v] > dfn[u] 永远不成立。

常见错误现象：bridge[i] = bridge[i^1] = true 从不触发，或所有边都被漏判为非桥。

强连通 Tarjan 不记录父边 ID，无法跳过刚走过来的那条反向边
无向图桥判定必须显式传入当前边编号（如 tarjan(v, i)），并在遍历时用 i != (fa ^ 1) 过滤父子边
强连通版本默认允许跨 SCC 回溯，而桥判定要求严格区分树边与非树边

无向图桥判定的正确 Tarjan 实现关键点

必须使用专为无向图改造的 Tarjan 版本，重点在父子边过滤和 low 更新时机：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

递归调用写成 tarjan(v, i)，其中 i 是当前遍历的边索引
循环中遇到已访问节点 v 时，仅当 i != (fa ^ 1) 才用 dfn[v] 更新 low[u]（fa ^ 1 是反向边编号）
回溯后检查 low[v] > dfn[u] —— 注意是严格大于，无等号
dfn 和 low 数组初始化为 0，未访问节点靠 !dfn[v] 判断

示例片段（邻接表建图，边从 2 开始编号）：

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++num;
    for (int i = head[u]; i; i = Next[i]) {
        int v = ver[i];
        if (i == (fa ^ 1)) continue; // 跳过父边
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = true;
        } else {
            low[u] = min(low[u], dfn[v]); // 只用 dfn[v]，不用 low[v]
        }
    }
}