难度: Hard
力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有 关键连接 。
示例 1：
输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] 输出：[[1,3]] 解释：[[3,1]] 也是正确的。
示例 2:
输入：n = 2, connections = [[0,1]] 输出：[[0,1]]
提示：
2 <= n <= 105n - 1 <= connections.length <= 1050 <= ai, bi <= n - 1ai != bi运行时间: 305 ms
内存: 60.2 MB
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
g = [[] for _ in range(n)]
# 建立边
for x,y in connections:
g[x].append(y)
g[y].append(x)
ids = [-1] * n
res = []
def dfs(x,fa,cur_id):
ids[x] = cur_id
# 更新id
# 枚举相邻节点
for y in g[x]:
if y == fa:continue
elif ids[y] == -1:
ids[x] = min(dfs(y,x,cur_id + 1),ids[x])
else:
ids[x] = min(ids[x],ids[y])
# x 节点的id更新完毕后，判断它和父节点的边是否是桥边
if ids[x] == cur_id and cur_id != 0:
res.append((x,fa))
return ids[x]
dfs(0,-1,0)
return res
这个题解使用了Tarjan算法来查找无向图中的桥（关键连接）。该算法通过深度优先搜索（DFS）来遍历图，并使用一个数组ids来记录每个节点在DFS树中的编号。对于每个节点，我们用它的编号初始化ids数组，然后在DFS过程中更新ids值。如果一个节点的编号等于它在ids数组中的值，且它不是根节点，那么该节点与它的父节点之间的边就是一座桥。这是因为从根节点到该节点的路径上没有其他路径可以到达该节点。
时间复杂度: O(V+E)
空间复杂度: O(V+E)
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
g = [[] for _ in range(n)] # 创建邻接表表示图
# 建立图的边
for x,y in connections:
g[x].append(y)
g[y].append(x)
ids = [-1] * n # 初始化每个节点的编号为-1
res = [] # 存储结果的列表
def dfs(x,fa,cur_id):
ids[x] = cur_id # 设置当前节点的编号
# 遍历当前节点的所有邻居
for y in g[x]:
if y == fa: continue # 跳过父节点
elif ids[y] == -1: # 如果邻居节点未被访问过
ids[x] = min(dfs(y,x,cur_id + 1),ids[x]) # 更新当前节点的编号
else:
ids[x] = min(ids[x],ids[y]) # 更新当前节点的编号
# 检查当前节点和父节点之间的边是否是桥
if ids[x] == cur_id and cur_id != 0:
res.append((x,fa))
return ids[x]
dfs(0,-1,0) # 从节点0开始深度优先搜索
return res
在Tarjan算法中，使用数组ids来记录每个节点在深度优先搜索（DFS）中的访问编号是为了帮助识别图中的桥。每个节点在第一次被访问时被分配一个唯一的编号，这个编号反映了它在DFS遍历中的访问顺序。通过比较节点及其邻居的编号，算法可以确定某个节点是否能够通过另一条非直接连接的路径连接回它的祖先节点，从而判断一个节点与其父节点之间的连接是否是桥。如果从一个节点到其任何祖先的其他路径不存在，则该连接为桥。
在图中存在环的情况下，Tarjan算法通过检查已访问的邻居节点的ids值来处理环。当遇到一个已访问的邻居节点时，算法会使用这个邻居的ids值来更新当前节点的ids值。如果通过邻居节点可以找到一条到达当前节点祖先的路径，那么当前节点的ids值会被更新为较小的值，表示当前节点通过邻居节点可以回溯到更早的祖先节点。这种更新机制确保了算法可以正确处理环的存在，不会错误地将环内的连接标记为桥。
在Tarjan算法中，如果一个节点的ids值在DFS完成后仍然等于其初始时分配的编号，并且该节点不是根节点，这表明从该节点到其父节点的连接没有其他替代路径。也就是说，即使该节点与其父节点之间的直接连接被去除，也没有其他路径可以从该节点回到它的任何祖先节点。这样的边被称为桥，因为它是连接两个分离部分的唯一路径。
在题解中的`dfs`函数递归调用时，参数`cur_id`递增是为了确保每个节点在DFS遍历中都能获得一个唯一且递增的访问编号。这个编号帮助算法跟踪遍历的顺序和构建DFS树。递增`cur_id`的作用是为每个新访问的节点提供一个新的、比之前所有节点都大的编号，这有助于算法后续判断节点间的连接关系，尤其是在检测桥的过程中非常关键。每个节点的编号不仅代表了它的访问顺序，还作为一个标记，用于判断是否有其他路径可以到达该节点的祖先。