1192. Critical Connections in a Network

[Woodyiiiiiii]

这道题使用了Tarjan算法。

Tarjan算法是在O(n+e)时间复杂度上用深度优先遍历方法解决图的强连通问题(包括割点、桥)的算法。

class Solution {
    
    // map
    Map<Integer, List<Integer>> map;
    
    // 时序数组
    int[] low;
    
    // 访问数组
    int[] v;
    
    // 访问指针
    int t = 1;
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        
        buildMap(connections);
        low = new int[n];
        v = new int[n];
        
        List<List<Integer>> res = new ArrayList<>();
        
        dfs(0, -1, res);
        
        return res;
        
    }
    
    private void buildMap(List<List<Integer>> connections) {
        
        map = new HashMap<>();
        
        for (List<Integer> con : connections) {
            int i = con.get(0);
            int j = con.get(1);
            if (!map.containsKey(i)) {
                map.put(i, new ArrayList<>());
            }
            if (!map.containsKey(j)) {
                map.put(j, new ArrayList<>());
            }
            map.get(i).add(j);
            map.get(j).add(i);
        }
        
    }
    
    private void dfs(int start, int parent, List<List<Integer>> res) {
        
        v[start] = low[start] = t++;
        
        List<Integer> cons = map.get(start);
        for (int next : cons) {
            if (v[next] == 0) {
                dfs(next, start, res);
                low[start] = Math.min(low[start], low[next]);
            } else if (next != parent) {
                low[start] = Math.min(low[start], v[next]);
            }
            
            if (low[next] > v[start]) {
                res.add(Arrays.asList(start, next));
            }
        }
        
    }
    
}

---

参考资料：

• 原题地址
• 中文官网解法
• https://leetcode.com/problems/critical-connections-in-a-network/discuss/1174196/JS-Python-Java-C%2B%2B-or-Tarjan's-Algorithm-Solution-w-Explanation
• 讲解视频