图中的桥和割点是什么？Tarjan 算法如何找到它们？

简化版

桥是无向图中删除后会让连通分量数量增加的边；割点是删除后会让连通分量数量增加的点。

Tarjan 算法通过 DFS 时间戳 dfn 和能回到的最早祖先 low 来判断它们。对于树边 u -> v，如果 low[v] > dfn[u]，边 (u, v) 是桥；如果 low[v] >= dfn[u]，u 可能是割点，但根节点要单独判断子树数量。

详细版

DFS 时记录：

字段	含义
`dfn[u]`	节点 `u` 第一次被访问的时间
`low[u]`	`u` 或其子树通过返祖边能到达的最早时间戳

判断桥：

low[v] > dfn[u]

说明 v 的子树无法绕回 u 或 u 的祖先，删掉 (u, v) 后图会断开。

判断割点：

low[v] >= dfn[u]

说明 v 子树无法绕过 u 回到更早节点，u 对连通性很关键。

完整版教学

1. 桥是什么

桥，也叫割边。

在无向图中，如果删除一条边后，原本连通的部分被分成两块或更多，这条边就是桥。

例如一条连接两个社区的唯一道路：

A -- B -- C

删除 B-C 后，C 就和前面断开。

2. 割点是什么

割点是删除某个点及其相关边后，会让连通分量数量增加的点。

它表示网络中的关键节点。

概念	删除对象	影响
桥	边	图断开
割点	点	图断开

桥和割点常用于网络可靠性分析、路由冗余分析、社交网络关键节点识别。

3. dfn 和 low 分别表示什么

Tarjan DFS 中常维护两个数组。

dfn[u] 表示节点 u 被第一次访问的时间。

low[u] 表示从 u 或 u 的 DFS 子树出发，通过树边和最多一条返祖边，能回到的最早节点时间。

low 值回答的是：这个子树有没有路能绕回祖先。

4. 桥的判断为什么是 low[v] > dfn[u]

假设 DFS 树边是 u -> v。

如果 low[v] > dfn[u]，说明 v 子树里没有任何边能回到 u 或 u 的祖先。

那么 u-v 就是连接 v 子树和外部的唯一通道。

删掉这条边，v 子树会断开，所以它是桥。

5. 割点的判断为什么是 low[v] >= dfn[u]

对于非根节点 u，如果存在一个子节点 v 满足：

low[v] >= dfn[u]

说明 v 子树无法绕过 u 回到 u 的祖先。

删除 u 后，v 子树会和外部断开，所以 u 是割点。

这里是 >=，不是 >，因为即使只能回到 u 自己，删除 u 后也没用了。

6. 根节点为什么要特殊处理

DFS 根节点没有祖先。

根节点是否是割点，取决于它在 DFS 树中有多少个独立子树。

如果根节点有至少 2 个 DFS 子树，删除根后这些子树之间无法互相到达，根就是割点。

节点类型	割点判断
非根节点	存在子节点 `low[v] >= dfn[u]`
根节点	DFS 子树数量大于等于 `2`

7. 伪代码骨架

核心 DFS 逻辑如下：

dfs(u, parent):
  dfn[u] = low[u] = ++time
  childCount = 0
  for v in graph[u]:
    if v not visited:
      childCount++
      dfs(v, u)
      low[u] = min(low[u], low[v])
      if low[v] > dfn[u]: edge(u, v) is bridge
      if parent != null and low[v] >= dfn[u]: u is articulation
    else if v != parent:
      low[u] = min(low[u], dfn[v])

根节点割点判断在 DFS 后根据 childCount 处理。

8. 常见误区与追问

误区：桥和割点是一回事。 桥是边，割点是点，判断条件也不同。
误区：判断桥用 >=。 桥要求 low[v] > dfn[u]，等于表示还能回到 u。
误区：根节点割点也用普通公式。 根节点没有祖先，必须看 DFS 子树数量。
追问：Tarjan 的复杂度是多少？ DFS 遍历点和边，复杂度是 O(V + E)。
追问：有向图也这样找桥吗？ 这里讨论的是无向图，有向图连通性问题通常要换成强连通分量等概念。

简化版

详细版