Hard

题目描述

有 n 个服务器，编号从 0 到 n - 1，它们之间通过服务器到服务器的连接形成一个网络，其中 connections[i] = [ai, bi] 表示服务器 ai 和 bi 之间的连接。任何服务器都可以直接或间接地通过网络到达其他服务器。

关键连接 是指如果移除该连接，会导致某些服务器无法到达其他某些服务器的连接。

返回网络中所有关键连接，顺序任意。

示例 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 <= 10^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 没有重复的连接

解题思路

这道题要求找出图中的桥（关键连接），即删除后会增加连通分量数目的边。这是一个经典的图论问题，最优解法是使用 Tarjan 算法。

核心思路

Tarjan 算法的关键概念：

  • 发现时间（discovery time）：DFS 遍历中首次访问节点的时间戳
  • 低值（low value）：从当前节点出发，通过DFS能够访问到的最小发现时间

算法步骤

  1. 建图：将连接列表转换为邻接表表示
  2. DFS遍历：对每个未访问的节点进行深度优先搜索
  3. 计算low值：
    • 初始时，low[u] = disc[u]
    • 对于邻接节点v：
      • 如果v未访问：递归DFS，然后更新 low[u] = min(low[u], low[v])
      • 如果v已访问且不是父节点：更新 low[u] = min(low[u], disc[v])
  4. 识别桥：对于边(u,v)，如果 low[v] > disc[u]，则该边是桥

为什么这样判断？

如果 low[v] > disc[u]，说明从v出发无法通过后向边回到u或u的祖先，因此删除边(u,v)会断开连通性。

时间复杂度：O(V + E)，空间复杂度：O(V + E)，其中V是节点数，E是边数。

代码实现

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> graph(n);
        for (auto& conn : connections) {
            graph[conn[0]].push_back(conn[1]);
            graph[conn[1]].push_back(conn[0]);
        }
        
        vector<int> disc(n, -1), low(n, -1);
        vector<bool> visited(n, false);
        vector<vector<int>> result;
        int time = 0;
        
        function<void(int, int)> dfs = [&](int u, int parent) {
            visited[u] = true;
            disc[u] = low[u] = time++;
            
            for (int v : graph[u]) {
                if (v == parent) continue;
                
                if (!visited[v]) {
                    dfs(v, u);
                    low[u] = min(low[u], low[v]);
                    
                    if (low[v] > disc[u]) {
                        result.push_back({u, v});
                    }
                } else {
                    low[u] = min(low[u], disc[v]);
                }
            }
        };
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, -1);
            }
        }
        
        return result;
    }
};

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        disc = [-1] * n
        low = [-1] * n
        visited = [False] * n
        result = []
        time = [0]
        
        def dfs(u, parent):
            visited[u] = True
            disc[u] = low[u] = time[0]
            time[0] += 1
            
            for v in graph[u]:
                if v == parent:
                    continue
                
                if not visited[v]:
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    
                    if low[v] > disc[u]:
                        result.append([u, v])
                else:
                    low[u] = min(low[u], disc[v])
        
        for i in range(n):
            if not visited[i]:
                dfs(i, -1)
        
        return result

public class Solution {
    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var conn in connections) {
            graph[conn[0]].Add(conn[1]);
            graph[conn[1]].Add(conn[0]);
        }
        
        var disc = new int[n];
        var low = new int[n];
        var visited = new bool[n];
        var result = new List<IList<int>>();
        var time = new int[1];
        
        for (int i = 0; i < n; i++) {
            disc[i] = low[i] = -1;
        }
        
        void Dfs(int u, int parent) {
            visited[u] = true;
            disc[u] = low[u] = time[0]++;
            
            foreach (int v in graph[u]) {
                if (v == parent) continue;
                
                if (!visited[v]) {
                    Dfs(v, u);
                    low[u] = Math.Min(low[u], low[v]);
                    
                    if (low[v] > disc[u]) {
                        result.Add(new List<int> { u, v });
                    }
                } else {
                    low[u] = Math.Min(low[u], disc[v]);
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Dfs(i, -1);
            }
        }
        
        return result;
    }
}

var criticalConnections = function(n, connections) {
    const graph = Array(n).fill().map(() => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const low = new Array(n);
    const disc = new Array(n);
    const visited = new Array(n).fill(false);
    const result = [];
    let time = 0;
    
    function dfs(u, parent) {
        visited[u] = true;
        disc[u] = low[u] = time++;
        
        for (const v of graph[u]) {
            if (v === parent) continue;
            
            if (!visited[v]) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                
                if (low[v] > disc[u]) {
                    result.push([u, v]);
                }
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, -1);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(V + E) - 其中 V 是节点数，E 是边数。每个节点和每条边都只访问一次
空间复杂度O(V + E) - 邻接表存储图需要 O(V + E) 空间，递归栈最深 O(V)