LeetCode 1192. Critical Connections in a Network

原题链接在这里：https://leetcode.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] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

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

Return all critical connections in the network in any order.

Example 1:

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

Constraints:

• 1 <= n <= 10^5
• n-1 <= connections.length <= 10^5
• connections[i][0] != connections[i][1]
• There are no repeated connections.

题解：

How to find the bridge of connected graph, we need to find the edge that is not in the cycle.

Then how to find the edge that is not in the cycle. Iterate from one starting node, mark it as visited and the time it has been visited.

Perform DFS for its neighbors, and track the lowest node that this node could reach out to.

When its id < lowest node it could reach out to, then (u, v) is a critical edge.

When meeting a node v that has been visited before, update current node u low with ids[v].

When backtracking, update current node u low with DFS next node v low[v].

Thus DFS state needs to know current node, low array, ids array, graph, res and parent node.

Since this is undirected graph, we want parent to avoid DFS to parent.

Time Complexity: (n + connections.size()). DFS takes O(V + E). each node is only traversed no more than 2 times.

Space: O(v).

AC Java: 

1 1 class Solution {
2 2     int id = 0;
3 3     
4 4     public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
5 5         List<List<Integer>> res = new ArrayList<>();
6 6         if(n < 1){
7 7             return res;
8 8         }
9 9         
1010         List<Integer> [] graph = new ArrayList[n];
1111         for(int i = 0; i < n; i++){
1212             graph[i] = new ArrayList<>();
1313         }
1414         
1515         for(List<Integer> e : connections){
1616             graph[e.get(0)].add(e.get(1));
1717             graph[e.get(1)].add(e.get(0));
1818         }
1919         
2020         int [] ids = new int[n];
2121         Arrays.fill(ids, -1);
2222         int [] low = new int[n];
2323         
2424         for(int i = 0; i < n; i++){
2525             if(ids[i] == -1){
2626                 dfs(i, low, ids, graph, res, -1);
2727             }
2828         }
2929         
3030         return res;
3131     }
3232     
3333     private void dfs(int u, int [] low, int [] ids, List<Integer> [] graph, List<List<Integer>> res, int parent){
3434         ids[u] = low[u] = ++id;
3535         List<Integer> neibors = graph[u];
3636         
3737         for(int v : neibors){
3838             if(v == parent){
3939                 continue;
4040             }
4141             
4242             if(ids[v] == -1){
4343                 dfs(v, low, ids, graph, res, u);
4444                 low[u] = Math.min(low[u], low[v]);
4545                 
4646                 if(low[v] > ids[u]){
4747                     res.add(Arrays.asList(u, v));
4848                 }
4949             }else{
5050                 low[u] = Math.min(low[u], ids[v]);
5151             }
5252         }
5353     }
5454 }