LeetCode 1192. 查找集群内的关键连接

题目描述
有一个网络包含 n 个服务器，编号从 0 到 n-1，它们通过无向的服务器到服务器连接（即“边”）相连。任意两个服务器之间可能存在多条直接连接。
“关键连接”是指这样一条连接：如果它被移除，会导致某些服务器之间无法互相访问。
给定一个整数 n 和一个连接列表 connections，其中每个 connections[i] = [a, b] 表示服务器 a 和 b 之间的连接。你需要找出网络中的所有关键连接，并以任意顺序返回它们。

举个例子：
输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出：[[1,3]]
解释：移除连接 [1,3] 后，服务器 3 将无法与任何其他服务器通信。而其他连接移除后，所有服务器仍能互相访问。

解题过程循序渐进讲解

步骤1：理解问题本质
这道题实际上是在一个无向连通图中寻找所有的“桥”（bridge）。

• 桥：一条边，如果去掉它，图的连通分量数量会增加（即图变得不连通，或某些点被隔离）。
• 关键连接 = 桥。
  所以我们需要一个高效的算法来找出无向图中的所有桥。

步骤2：暴力法思路与缺点
最直接的想法是：

1. 枚举每一条边。
2. 暂时去掉这条边，然后检查图的连通性（比如用 BFS/DFS 遍历整个图，看是否所有点都能访问到）。
3. 如果去掉后图不再连通，那么这条边是关键连接。
   时间复杂度：O(E * (V+E))，在 n 最多 10^5 时不可行。
   我们需要 O(V+E) 的算法。

步骤3：Tarjan 找桥算法（基于 DFS 时间戳）
这是一个经典算法，用一次 DFS 就可以找出所有桥。核心思想是：

• 在 DFS 过程中，给每个节点记录两个值：
  • disc[u]：节点 u 被第一次访问的时间（DFS 进入时间戳，从 0 开始递增）。
  • low[u]：从 u 出发，通过 DFS 树边以及一条反向边（即指向祖先或兄弟的后向边）能到达的最早的节点的 disc 值。
• 对于一条边 u-v（假设 DFS 中先访问 u 再访问 v），如果 low[v] > disc[u]，那么 u-v 是桥。
  为什么？
  low[v] 表示 v 能绕回到的最早的节点的时间戳。如果 low[v] > disc[u]，意味着 v 及其子树无法通过任何非父边回到 u 或 u 的祖先，那么去掉 u-v 后，v 的子树就和 u 不连通了，所以是桥。
  如果 low[v] <= disc[u]，说明 v 能通过其他路径回到 u 或 u 的祖先，那么 u-v 就不是桥。

步骤4：算法详细步骤

1. 构建无向图的邻接表。
2. 初始化：
   • 一个全局时间戳 time = 0。
   • disc 数组全为 -1（表示未访问）。
   • low 数组初始为 0。
3. DFS 函数设计（参数：当前节点 u，父节点 parent）：
   • 标记 u 已访问：disc[u] = low[u] = ++time。
   • 遍历 u 的所有邻居 v：
     • 如果 v 未访问（disc[v] == -1）：
       • 递归 DFS(v, u)。
       • 递归返回后，更新 low[u] = min(low[u], low[v])。
       • 检查桥条件：如果 low[v] > disc[u]，则边 u-v 是桥，加入结果列表。
     • 如果 v 已访问且 v != parent（说明是反向边）：
       • 更新 low[u] = min(low[u], disc[v])。
4. 从任一节点开始 DFS（因为图是连通的，题目没说，但实际可能不连通？注意：题目给的 n 个服务器，connections 可能不连通，我们需要对每个未访问节点 DFS，但不连通时单独的边也可能是关键连接）。
5. 返回所有找到的桥。

步骤5：实例推演
以 n=4, connections=[[0,1],[1,2],[2,0],[1,3]] 为例：

• 建图：0-1, 1-2, 2-0, 1-3。
• 从节点 0 开始 DFS，时间戳从 1 开始。

DFS(0, parent=-1):
disc[0]=1, low[0]=1。
邻居 1（未访问）→ DFS(1,0)。

DFS(1,0):
disc[1]=2, low[1]=2。
邻居 0（已访问，是 parent，跳过）。
邻居 2（未访问）→ DFS(2,1)。

DFS(2,1):
disc[2]=3, low[2]=3。
邻居 1（已访问，是 parent，跳过）。
邻居 0（已访问，不是 parent）：更新 low[2] = min(low[2], disc[0]) = min(3,1)=1。
返回，更新 low[1] = min(low[1], low[2]) = min(2,1)=1。
检查边 1-2：low[2]=1, disc[1]=2，low[2] < disc[1]，不是桥。

回到 DFS(1) 继续：
邻居 3（未访问）→ DFS(3,1)。

DFS(3,1):
disc[3]=4, low[3]=4。
邻居 1（已访问，是 parent，跳过）。
返回，更新 low[1] = min(low[1], low[3]) = min(1,4)=1。
检查边 1-3：low[3]=4, disc[1]=2，low[3] > disc[1] → 是桥，加入结果 [[1,3]]。

最终结果：[[1,3]]。

步骤6：注意事项

• 图可能不连通，需要对每个连通分量分别 DFS。
• 由于是无向图，邻接表里每条边存两次。
• 递归深度可能很大（n 可达 10^5），可以用栈迭代或设置递归深度限制，但 Python 中递归可能需改迭代或使用 sys.setrecursionlimit。

步骤7：复杂度

• 时间 O(V+E)，每个节点和边访问一次。
• 空间 O(V+E) 用于存储图和递归栈。

步骤8：代码框架（Python）

from collections import defaultdict
class Solution:
    def criticalConnections(self, n, connections):
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        disc = [-1] * n
        low = [0] * n
        time = 0
        bridges = []
        
        def dfs(u, parent):
            nonlocal time
            disc[u] = low[u] = time
            time += 1
            for v in graph[u]:
                if v == parent:
                    continue
                if disc[v] == -1:  # 未访问
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    if low[v] > disc[u]:
                        bridges.append([u, v])
                else:  # 已访问，且不是父节点，是反向边
                    low[u] = min(low[u], disc[v])
        
        for i in range(n):
            if disc[i] == -1:
                dfs(i, -1)
        return bridges

这个算法就是 Tarjan 找桥算法，一次 DFS 即可高效找出所有关键连接。