LeetCode 题解工作台
查找集群内的关键连接
力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络， connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·DFS·traversal
答案摘要
此题中的「关键连接」即为「桥」。 「桥」：在一连通的无向图中，若去除某一边后会使得图不再连通，则这条边可以视作「桥」。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
力扣数据中心有 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- 不存在重复的连接
解题思路
方法一：Tarjan 算法
此题中的「关键连接」即为「桥」。
「桥」：在一连通的无向图中，若去除某一边后会使得图不再连通，则这条边可以视作「桥」。
与之相应的概念还有「割点」。
「割点」：在一连通的无向图中，若去除某一点及所有与其相连的边后会使得图不再连通，则这个点可以视作「割点」。
用于求图中的「桥」与「割点」有一算法：tarjan 算法，这个算法使用先递归的访问相邻节点后访问节点自身的 dfs 方法，通过记录「访问的顺序：DFN」以及在递归结束后访问节点自身时探索其可以回溯到的最早被访问的节点来更新「最早可回溯的节点：low」，可以实现在 时间内找到图的「桥」与「割点」。同时，此种算法可以用于查找有向图中的强连通分量。
class Solution:
def criticalConnections(
self, n: int, connections: List[List[int]]
) -> List[List[int]]:
def tarjan(a: int, fa: int):
nonlocal now
now += 1
dfn[a] = low[a] = now
for b in g[a]:
if b == fa:
continue
if not dfn[b]:
tarjan(b, a)
low[a] = min(low[a], low[b])
if low[b] > dfn[a]:
ans.append([a, b])
else:
low[a] = min(low[a], dfn[b])
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append(b)
g[b].append(a)
dfn = [0] * n
low = [0] * n
now = 0
ans = []
tarjan(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to implement depth-first search and handle graph traversal efficiently.
- question_mark
Assess understanding of Tarjan's algorithm and its application to finding critical connections.
- question_mark
Evaluate how the candidate handles edge cases, such as small or sparse graphs, and ensures correctness.
常见陷阱
外企场景- error
Failing to correctly track low and discovery times in the DFS process can lead to incorrect identification of critical connections.
- error
Ignoring edge cases, such as when there are very few connections or the network is already disconnected.
- error
Not considering the constraint that the network has no repeated connections, which affects how the graph is processed.
进阶变体
外企场景- arrow_right_alt
Finding all bridges in a directed graph with similar conditions.
- arrow_right_alt
Optimizing for very large graphs with hundreds of thousands of nodes and edges.
- arrow_right_alt
Implementing an iterative version of Tarjan's algorithm to avoid recursion depth issues in large graphs.