题目

力扣数据中心有 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]]

解析

做这道题首先要知道Tarjan 算法，它可以找到网络中的所有“桥”或“关键连接”，首先要知道关键概念：

1. Low-link Value：对于图中的每个节点，low-link value 是该节点或通过其可达的任何节点可以追溯到的最早的节点的序号。
2. Discovery Time：节点在 DFS 遍历中第一次被发现的时间戳。

它的步骤如下：

1. 使用 Depth-First Search (DFS) 遍历图。

2. 维护每个节点的 discovery time 和 low-link value。

3. 为每个节点分配一个唯一的 discovery time 值，初始时设置其 low-link value 为与其 discovery time 相同。

4. 访问每个节点的邻居：

   • 如果这个邻居还没有被访问过（意味着 discovery time 是无限），递归访问它，完成后更新当前节点的 low-link value。
   • 如果邻居已经被访问过（意味着是后向边），更新当前节点的 low-link value 为当前节点和邻居节点的 low-link value 的最小值。

5. 在从 DFS 返回时，如果某个节点的 low-link value 等于其 discovery time，并且它不是起始节点，那么它与其父节点的连接就是一个桥。

是不是觉得很抽象？那就需要看这道题来彻底理解这个算法，同时也可以用这个算法解决这道题目 这是AC代码，那么我将会在注释上去详细解释做这道题的思路

class Solution {
    int time = 0;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer>[] graph = new ArrayList[n + 1];
        for(int i = 0;i <= n;i ++) {
            graph[i] = new ArrayList<>();
        }
        // 构建图
        for(List<Integer> c : connections) {
            graph[c.get(0)].add(c.get(1));
            graph[c.get(1)].add(c.get(0));
        }
        // 两个discover和low数组
        int[] disc = new int[n + 1];
        Arrays.fill(disc, -1);  // 原先先赋值为-1，表示没有访问过
        int[] low = new int[n + 1];
        // 接着遍历所有没有访问过的节点
        for(int i = 0 ;i < n;i ++) {
            if(disc[i] == -1) {
                dfs(i, i, disc, low, graph, ans);
            }
        }
        return ans;
    }
    
    public void dfs(int u, int parent, int[]disc, int[] low, List<Integer>[] graph, List<List<Integer>> ans) {
        disc[u] = low[u] = ++time;  // 每一个节点遍历到的时候就赋值为time，递增++
        for(int g : graph[u]) {
            if(g == parent) {  // 如果又是父节点则跳过
                continue;
            }
            if(disc[g] == -1) {  // 没有遍历过则进入到dfs，去更信low值
                dfs(g, u, disc, low, graph, ans);
                low[u] = Math.min(low[u], low[g]);  // 这个更新low值其实就是拿子节点的low值更新这个节点
                if(low[g] > disc[u]) {  // 这是关键---代表着没有其他路可以通向这里，就无法更新到更小的值 
                    ans.add(Arrays.asList(u, g));
                }
            } else {  // 如果访问过的话，就拿子节点第一次的遍历时间更新此节点的low值
                low[u] = Math.min(low[u], disc[g]);
            }
        } 
    }
}