StarWalker

Where my heart will take me

0%

Leetcode1192-criticalConnectionsInANetwork

Posted on Edited on In Views: Valine:
Solution Report of LeetCode Acceptted

Description

1
2
3
4
5
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
2
3
4
5
6
7
8
9
10
11
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[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.

Solution

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
class Solution {
    int time = 0;
    List<List<Integer>> res = new ArrayList<>();

    public void dfs(int u, List<List<Integer>> graph, int[] disc, int[] low, int[] parent, boolean[] visited){
        visited[u] = true;
        disc[u] = low[u] = ++ time;
        for (int v : graph.get(u)){
            if (!visited[v]){
                parent[v] = u;
                dfs(v, graph, disc, low, parent,visited);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]){
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(u);
                    tmp.add(v);
                    res.add(tmp);
                }
                    
            }
            else{
                if (v != parent[u]){
                    low[u] = Math.min(low[u], disc[v]);
                }
            }
        }        
    }
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++){
            graph.add(new ArrayList<Integer>());
        }
        for (List<Integer> pair : connections){
            int u = pair.get(0);
            int v = pair.get(1);
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        boolean[] visited = new boolean[n];
        int[] disc = new int[n];
        int[] low = new int[n];
        int[] parent = new int[n];
        for (int i = 0 ; i < n; i++){
            visited[i] = false;
            parent[i] = -1;
        }
    
        dfs(0, graph, disc, low, parent,visited);
        return res;
        
    }
}