力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器
的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b]
表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

关键连接 __ 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。

请你以任意顺序返回该集群内的所有 关键连接 。

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/original_images/critical-connections-in-a-network.png)

**输入：** 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 <= 105
0 <= ai, bi <= n - 1
ai != bi
不存在重复的连接

Problem: 1192. 查找集群内的关键连接

[TOC]

Code

[]
class Solution {
    int id=0;List<List<Integer>>res;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> con) {
        List<Integer>[]adt=new ArrayList[n];
        for(int i=0;i<n;i++)adt[i]=new ArrayList<>();
        for(var lis:con){
            int u=lis.get(0);int v=lis.get(1);
            adt[u].add(v);adt[v].add(u);
        }
        res=new ArrayList<>();
        int dfn[]=new int[n];int low[]=new int[n];
        
        dfs(0,0,adt,dfn,low);
        return res;
    }
    void dfs(int u,int p,List<Integer>[] adt,int []dfn,int [] low){
        low[u]=dfn[u]=++id;
        for(int v:adt[u]){
            if(dfn[v]==0){
                dfs(v,u,adt,dfn,low);
                low[u]=Math.min(low[u],low[v]);
                if(low[v]>dfn[u])res.add(Arrays.asList(u,v));
            }
            else if(dfn[v]<dfn[u] && v !=p){
                low[u]=Math.min(low[u],dfn[v]);
            }
        }
    }
}

1192-查找集群内的关键连接

Code