Leetcode: Critical Connections in a Network

 This Question is extremely frequently asked at Amazon. Sometimes it is asked at Adobe. 

Here is the question: 

There are n servers numbered from 0 to n - 1 connected connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. A critical connection is a connection that will make some server unable to reach some other server. Remove all the critical connections in the network in any order. Here is an example: 

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]]

Explanation: [[3,1]] is also accepted.

And from definition we can tell that an edge is a critical connection, if and only if it is not in a cycle. This means that we need to delete all the nodes from certain cycles.  

The starting node has rank 0 and all other nodes have a rank of -2. We increase the rank of each node as we move nodes, and then when we find a node with a lesser rank of 0 <= p < k if we are supposed to denote with length k, if a node has rank p, this means that we found a cycle. 

Let's have the depth-first-search function return the minimum rank that it finds. If dfs(v) returns something smaller or equal to rank(u), then you know that its neighbor has a cycle, so the edge is subsequently discarded. As a result, the remaining edges are the critical edges. 

Here's the code with its explanation and implementation: 

class Solution {

    int dfs(List<Integer>[] graph, int node, int depth, int[] rank, HashSet<List<Integer>> connectionSet) {

    //This node is already visited, no need to visit it again. 

    if(rank[node] >= 0 ) return rank[node];

    //set this rank of the node to the depth 

    rank[node] = depth;

    int minDepthFound = Integer.MAX_VALUE;

    //iterate through all the neighbors of this node

    for(Integer neighbor : graph[node]) {   

        //ignore the parent node. 

        if(rank[neighbor] == depth - 1) continue ;

        //perform dfs to have the minimum depth of the neighbor

        int minDepth = dfs(graph, neighbor, depth + 1, rank, connectionsSet);

        minDepthFound = Math.min(minDepthFound, minDepth);

        //If one of the successors of the neighbors has a depth less than current node, then we have a cycle.

         if(minDepth <= depth) {

            //remove the unnecessary nodes. 

            connectionsSet.remove(Arrays.asList(node, neighbor));

            connectionsSet.remove(Arrays.asList(neighbor, node)); 

         }

    }

    return minDepthFound;

}

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {

    List<Integer> graph = new ArrayList[n];

    //initialize an array of ArrayLists that lists the neighbors and connections to the graph. 

    for(int i = 0; i < n; i++) {

        graph[i] = new ArrayList<>();

    }

    //add each connection of the graph to the corresponding arrayList index

    for(List<Integer> oneConnection : connections) {

        graph[oneConnection.get(0)].add(oneConnection.get(1));

        graph[oneConnection.get(1)].add(oneConnection.get(0));

    //convert the connections to a hashset.

    HashSet<List<Integer>> connectionsSet = new HashSet<>(connections);

    int[] rank = new int[n];

    //All the ranks eventually starts with -2

    Arrays.fill(rank, -2);

    //remove all the critical connections and return this new list. 

    dfs(graph, 0, 0, rank, connectionsSet);

    return new ArrayList<>(connectionsSet);

}

}

This problem has O(|V| + |E|) time complexity.