桥与割点
找出会导致图断开的边和节点
桥与割点 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
图中的脆弱部分
无向图中的某些部分非常关键：移除它们后，图就会分裂。找到这些部分可以揭示薄弱连接。
什么是桥
桥是一条边，移除它会使连通分量的数量增加。它是两个区域之间的唯一通路。
什么是割点
割点是一个节点，移除它会使图变得不连通。网络最担心的就是这种单点故障。
再次使用 DFS 树
两种算法都基于一次 DFS，同时跟踪发现时间和 low 值，原理与 Tarjan算法相似，但应用于无向图。
disc = [-1] * n
low = [-1] * nLow 表示最早可达位置
节点的low是从其 DFS 子树可到达的最早发现编号，也可能是通过一条反向边向上到达的。
进入时初始化
当 DFS 进入一个节点时，将它的disc 和 low设为当前计时器的值，然后继续探索它的邻居。
disc[u] = low[u] = timer
timer += 1桥的判定条件
递归进入子节点 v 后，如果low[v] > disc[u]，就说明没有反向边越过 u，因此边 u-v 是一座桥。
if low[v] > disc[u]:
bridges.append((u, v))割点的判定条件
当非根节点 u 的某个子节点 v 满足low[v] >= disc[u]时，u 就是割点：v 的子树无法绕过 u。
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)根节点的特殊情况
DFS根节点只有在 DFS 树中拥有两个或更多子节点时才是割点，因此请对这些子节点进行计数。
if parent[u] == -1 and children > 1:
art.add(u)跳过父节点边
通过反向边更新 low 时，不要沿着指向父节点的边返回，否则会错误判断桥。
if v != parent[u]:
low[u] = min(low[u], disc[v])一遍遍历得到两个结果
一次 DFS 就能在O(V + E)时间内同时找到所有桥和割点。不需要额外遍历。
快速检查
从 u 递归进入子节点 v 后，您发现 low[v] > disc[u]。找到了什么？
回顾：关键边与节点
一次包含 disc 和 low 的 DFS 就能找到全部结果：low[v] > disc[u]表示一座桥，而 low[v] >= disc[u] 表示一个割点。🌉
常见问题解答
「桥与割点」课时是免费的吗？
是的 — 「桥与割点」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「桥与割点」这节课中我会学到什么？
找出会导致图断开的边和节点 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「桥与割点」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。