---

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

• 标签：深度优先搜索、图、双连通分量
• 难度：困难

题目链接

• 1192. 查找集群内的关键连接 - 力扣

题目大意

描述：有 $n$ 台服务器（编号 $0$ 到 $n-1$），服务器之间通过网络连接 $connections$ 相互连接，整个网络是连通的（任意两台服务器之间都直接或间接可达）。

关键连接：如果某条连接断开后，会导致某些服务器无法访问其他服务器，这条连接就是关键连接。用人话说就是：这条线一旦断了，网络就分成两半了。

要求：找出所有关键连接，以任意顺序返回。

说明：

• $2 \le n \le 10^5$。
• $n - 1 \le connections.length \le 10^5$。
• $0 \le a_i, b_i \le n - 1$。
• $a_i \ne b_i$。
• 不存在重复的连接。

示例：

输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出：[[1,3]]
解释：0-1-2 构成了一个三角形（环），即使断开其中任意一条，它们之间还有别的路走。但是 1-3 一旦断开，服务器 3 就彻底孤立了。

解题思路

思路 1：Tarjan 算法（找桥）

这个问题在计算机科学中叫做找桥（Bridge）。桥就是那些一旦删除，整个图就分成两部分的边。

直观地想一下：如果两条服务器之间有多条路径可以连接，那么任何一条连接断了都无所谓，因为还可以走别的路。但如果一条连接是唯一的通路，那它就是关键连接（桥）。

Tarjan 算法的核心思想是用 DFS（深度优先搜索，可以理解成「一条路走到黑，走不通再回头」）遍历整个网络，同时记录每个节点的一些重要信息，来判断连接是不是桥。

先理解几个概念：

1. 时间戳 $dfn[u]$： DFS 遍历时，节点 $u$ 是第几个被访问到的。这个编号就是时间戳。
2. 回溯值 $low[u]$： 从节点 $u$ 出发，不经过已经走过的路，能够到达的最早（时间戳最小）的节点。用人话说，就是看这个节点有没有「秘密捷径」能绕回到上面去。

判断桥的核心规则：

在 DFS 遍历时，如果从节点 $u$ 走到节点 $v$（$v$ 还没有被访问过），之后发现 $low[v] > dfn[u]$，这意味着：$v$ 不管怎么绕，都回不到 $u$ 或 $u$ 的祖先那里。那么边 $(u, v)$ 就是一条桥。

用人话比喻：你（$u$）发现你的小伙伴（$v$）除了你牵的这条线之外，没有任何其他途径能回到大部队，那你们之间的这根线就是唯一的命脉——不能断！

步骤拆解：

1. 建图。 先把连接关系转换成邻接表（每个服务器旁边有哪些服务器）。

2. 初始化两个数组。 $dfn$ 全部设为 $-1$（表示未访问），$low$ 也初始化为 $-1$。

3. 开始 DFS 遍历。 从任意节点出发（比如 0）：

   • 给当前节点 $u$ 打上时间戳 $dfn[u] = low[u] = timestamp$。
   • 遍历 $u$ 的所有邻居 $v$：
     • 如果 $v$ 是父节点，跳过（不走回头路）。
     • 如果 $v$ 没访问过： 递归处理 $v$。递归回来后，更新 $u$ 的回溯值：$low[u] = \min(low[u], low[v])$。
       • 如果这时 $low[v] > dfn[u]$，说明 $(u, v)$ 是一条桥，记录下来。
     • 如果 $v$ 已经访问过： 更新 $u$ 的回溯值：$low[u] = \min(low[u], dfn[v])$。

4. 返回所有找到的桥。

思路 1：代码

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # 第 1 步：建图，用邻接表表示
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        # dfn[u]：节点 u 被访问的时间戳
        # low[u]：节点 u 能回溯到的最早时间戳
        dfn = [-1] * n
        low = [-1] * n
        result = []
        timestamp = [0]  # 全局时间戳（用列表包起来，方便在函数里修改）
        
        def dfs(u, parent):
            """深度优先搜索，找出桥"""
            # 给当前节点分配时间戳
            dfn[u] = low[u] = timestamp[0]
            timestamp[0] += 1
            
            for v in graph[u]:
                # 跳过父节点，不走回头路
                if v == parent:
                    continue
                
                if dfn[v] == -1:  # v 还没有被访问过
                    dfs(v, u)       # 先递归访问 v
                    
                    # v 回来之后，更新 u 的回溯值
                    low[u] = min(low[u], low[v])
                    
                    # 核心判断：v 回不到 u 或 u 的祖先，(u, v) 就是桥
                    if low[v] > dfn[u]:
                        result.append([u, v])
                else:
                    # v 已经访问过了，用 v 的时间戳更新 u 的回溯值
                    low[u] = min(low[u], dfn[v])
        
        # 从节点 0 开始 DFS
        dfs(0, -1)
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n + m)$。用人话说就是：每个节点和每条边都恰好访问一次，$n$ 是节点数，$m$ 是边数。
• 空间复杂度：$O(n + m)$。需要存图（邻接表）、两个标记数组和递归调用的栈空间。