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

BCC双连通分量，https://leetcode.cn/problems/critical-connections-in-a-network/

力扣数据中心有 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 <= 105
n - 1 <= connections.length <= 10^5
0 <= ai, bi <= n - 1
ai != bi
不存在重复的连接

这道题要求寻找无向连通图中的所有“关键连接”（即桥）。在一个连通图中，如果删除某条边会使得图不再连通，那么这条边就是桥（Bridge）。

我们可以使用 Tarjan 算法（基于深度优先搜索 DFS）来高效地寻找所有的桥。

算法思路

在 DFS 遍历的过程中，我们为每个节点 $u$ 记录两个关键的值：

dfn[u]：节点 $u$ 被深度优先搜索到的次序号（时间戳）。
low[u]：节点 $u$ 或者是 $u$ 的子树中的节点，通过一条非树边（回边）能够到达的最小时间戳。

当我们在 DFS 树中从节点 $u$ 访问到节点 $v$ 时（且 $v$ 不是 $u$ 的父节点）：

如果 $v$ 还没有被访问过，我们递归地对 $v$ 进行 DFS。在 $v$ 的 DFS 结束后，我们用 low[v] 更新 low[u]（即 low[u] = min(low[u], low[v])）。
- 此时，如果满足 low[v] > dfn[u]，说明从 $v$ 及其子树出发，没有任何一条路径可以不通过边 (u, v) 访问到 $u$ 或其祖先。因此，边 (u, v) 就是一个关键连接（桥）。
如果 $v$ 已经被访问过，说明找到了一个环，我们用 dfn[v] 更新 low[u]（即 low[u] = min(low[u], dfn[v])）。

Python 3 实现

由于节点的数量最多为 $10^{5}$ ，递归深度可能会超过 Python 默认的限制，我们需要使用 sys.setrecursionlimit 来调大递归深度。

python

import sys
from typing import List

# 调大 Python 的最大递归深度以防止栈溢出
sys.setrecursionlimit(200000)

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # 1. 构建邻接表
        adj = [[] for _ in range(n)]
        for u, v in connections:
            adj[u].append(v)
            adj[v].append(u)
        
        dfn = [-1] * n
        low = [-1] * n
        bridges = []
        time = 0
        
        # 2. 定义 DFS 函数
        def dfs(u: int, parent: int):
            nonlocal time
            dfn[u] = low[u] = time
            time += 1
            
            for v in adj[u]:
                if v == parent:
                    continue
                if dfn[v] == -1:
                    # v 未被访问，递归访问
                    dfs(v, u)
                    # 更新当前节点的 low 值
                    if low[v] < low[u]:
                        low[u] = low[v]
                    # 判断是否为桥
                    if low[v] > dfn[u]:
                        bridges.append([u, v])
                else:
                    # v 已被访问，且不是父节点，更新当前节点的 low 值
                    if dfn[v] < low[u]:
                        low[u] = dfn[v]
                        
        # 因为整个网络是连通的，所以从任意节点（例如 0）开始 DFS 即可遍历所有的点
        dfs(0, -1)
        return bridges

复杂度分析

时间复杂度： $O (V + E)$ ，其中 $V = n$ 是服务器的数量， $E$ 是连接的数量。DFS 过程中每个顶点和每条边都只被访问了常数次。
空间复杂度： $O (V + E)$ 。邻接表需要 $O (V + E)$ 的空间，dfn 和 low 数组以及递归调用栈最多需要 $O (V)$ 的空间。

T1192.查找集群内的关键连接 ​

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