查找集群内的关键连接Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

tarjan找桥模板

# 解法


import java.util.*;

class Solution {
    int [] dfn  ;
    int [] low  ;
    ArrayList<Integer>[] map;
    int [] father;
    List<List<Integer>> lists;
    int times;


    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        lists = new ArrayList<>();
        father = new int[n];
        dfn = new int[n];
        low = new int[n];
        map = new ArrayList[n];
        times = 0;

        for (List<Integer> connection : connections) {

            if( map[connection.get(0)] == null)
            {
                map[connection.get(0)] = new ArrayList();
            }
            if( map[connection.get(1)] == null)
            {
                map[connection.get(1)] = new ArrayList();
            }
            map[connection.get(0)].add(connection.get(1));

            map[connection.get(1)].add(connection.get(0));
        }
        tarjan(0);
        return lists;
    }

    void tarjan ( int point)
    {
        dfn[point] = low[point] = ++times;

        for (int k = 0; k < map[point].size(); k++) {

            int i =  map[point].get(k);

            if(dfn[i] == 0)
            {
                father[i] = point;
                tarjan(i);

                if(low[i] > dfn[point])
                {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(point);
                    lists.add(temp);
                }
                low[point] = Math.min(low[point],low[i]);
            }
            if(father[point] != i)
            {
                low[point] = Math.min(low[point],low[i]);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# 总结

分析出几种情况，然后分别对各个情况实现