原文链接: https://leetcode-cn.com/problems/critical-connections-in-a-network

英文原文

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

 

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

 

Constraints:

• 2 <= n <= 105
• n - 1 <= connections.length <= 105
• 0 <= ai, bi <= n - 1
• ai != bi
• There are no repeated connections.

中文题目

力扣数据中心有 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]] 也是正确的。

 

提示：

• 1 <= n <= 10^5
• n-1 <= connections.length <= 10^5
• connections[i][0] != connections[i][1]
• 不存在重复的连接

通过代码

高赞题解

https://www.bilibili.com/video/BV15t4y197eq/
题目解释 + 思考方式 + 算法分析 + 复杂度分析 + Java代码说明

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // 构建一个map，存放每个节点的相邻节点有哪些
        Map<Integer, Set<Integer>> map = new HashMap<>();
        buildMap(connections, map);
        
        // 创建一个数组，存放每个节点的id是什么
        int[] id = new int[n];
        Arrays.fill(id, -1);
        
        // 选取一个点作为根节点，dfs向下递归，过程中识别出哪个边是critical connection
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, 0, -1, id, map, res);    // 假设根节点有一个编号是-1父节点
        
        return res;
    }
    
    public int dfs(int node, int nodeID, int par, int[] id, Map<Integer, Set<Integer>> map, List<List<Integer>> res){
        id[node] = nodeID;
        
        Set<Integer> set = map.get(node);
        for(Integer neighbor: set){
            if(neighbor == par){
                continue;
            }else if(id[neighbor] == -1){
                id[node] = Math.min(id[node], dfs(neighbor, nodeID + 1, node, id, map, res));
            }else{
                id[node] = Math.min(id[node], id[neighbor]);
            }
        }
        
        if(id[node] == nodeID && node != 0){
            res.add(Arrays.asList(par, node));
        }
        
        return id[node];
    }
    
    public void buildMap(List<List<Integer>> con, Map<Integer, Set<Integer>> map){
        for(List<Integer> edge : con){
            int n1 = edge.get(0);
            int n2 = edge.get(1);
            
            Set<Integer> n1n = map.getOrDefault(n1, new HashSet<>());
            Set<Integer> n2n = map.getOrDefault(n2, new HashSet<>());
            
            n1n.add(n2);
            n2n.add(n1);
            
            map.put(n1, n1n);
            map.put(n2, n2n);
        }
    }
}

统计信息

通过次数	提交次数	AC比率
4565	9106	50.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言