Problem Explanation

We are given n servers numbered from 0 to n-1, which are connected to form a network. The connections are undirected i.e., a connection from server a to server b implies that there is a connection from server b to server a. The connections are represented in the form of a 2-D array, where each element [a, b] represents a connection between server a and server b.

We need to find the critical connections in our network. A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Example

Let's consider an example where n = 4, and connections = [[0,1],[1,2],[2,0],[1,3]].

In this example, if we remove the connection [1, 3], server 3 will not be able to reach other servers (i.e., 0, 1, and 2). Hence [1, 3] is a critical connection.

Approach

To solve this problem, we can use the depth-first search (DFS) algorithm.

Step 1: Build an adjacency list (graph) of the servers using the provided connections.

Step 2: Initialize the rank with NO_RANK (-2) to indicate not visited.

Step 3: Use the DFS algorithm - start with server 0 (or any other server). The rank of a node (server) is the largest ordinal number used to visit this node or any node that this node can reach. If a node v visited from node u can reach a node visited before u (i.e., has a smaller rank), then u - v is not a critical connection.

Step 4: After the DFS, all the remaining edges are the answer. These edges are exactly the ones that don't form a back edge in the DFS traversal.

C++ Solution

1
2cpp
3class Solution {
4  static constexpr int NO_RANK = -2;
5public:
6    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
7        vector<vector<int>> graph(n);
8      
9        for (auto& conn : connections) {
10            graph[conn[0]].push_back(conn[1]);
11            graph[conn[1]].push_back(conn[0]);
12        }
13
14        vector<int> rank(n, NO_RANK);
15        vector<vector<int>> result;
16        dfs(graph, 0, 0, rank, result);
17        return result;
18    }
19
20    int dfs(vector<vector<int>>& graph, int node, int depth, vector<int>& rank, vector<vector<int>>& result) {
21        if (rank[node] >= 0) {
22            return rank[node];
23        }
24        rank[node] = depth;
25        int minBackDepth = depth;
26        for (auto neighbor : graph[node]) {
27            if (rank[neighbor] == depth - 1 || rank[neighbor] == graph.size()) {
28                continue;
29            }
30            int backDepth = dfs(graph, neighbor, depth + 1, rank, result);
31            minBackDepth = min(minBackDepth, backDepth);
32            if (backDepth <= depth) {
33                continue;
34            }
35            result.push_back({node, neighbor});
36        }
37        rank[node] = graph.size();
38        return minBackDepth;
39    }
40};

In the C++ solution above, we initialize a graph and rank vector then perform DFS on the graph. If a node is not visited (denoted by NO_RANK), we call dfs function on that node and update the rank of the node to the maximum ordinal number. We keep track of the minimum back depth. If the back depth of a node is greater than the current depth, we add this node to our result vector. After the DFS is done, we mark the node as visited by setting its rank to the size of the graph.

Our final result would be the vector where all the critical connections are stored.## Python solution

1
2python
3from collections import defaultdict
4from typing import List
5
6class Solution(object):
7    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
8        def makeGraph():
9            for conn in connections:
10                graph[conn[0]].append(conn[1])
11                graph[conn[1]].append(conn[0])
12
13        def dfs(rank, curr, prev):
14            low[curr] = rank
15            for neighbor in graph[curr]:
16                if neighbor == prev:
17                    continue
18                else: 
19                    if not low[neighbor]: 
20                        dfs(rank + 1, neighbor, curr)
21                    low[curr] = min(low[curr], low[neighbor])
22                    if low[neighbor] == rank + 1:
23                        res.append([curr, neighbor])    
24
25        graph = defaultdict(list)
26        res = []
27        low = [0 for _ in range(n)] 
28
29        makeGraph()
30        dfs(1, 0, -1)
31        return res

In the Python solution above, we initialize a graph and a low array then perform DFS on the graph. We keep the track of the lowest rank a node can reach without crossing the parent node. If a node is not visited, we call dfs function on that node and update the low value of the current node to the minimum of the low value of the current node and the low value of the neighbor node. If the low value of a neighbor is greater than the rank of the current node, we add this connection to our result list.

Our final result would be the list where all the critical connections are stored.

Java Solution

1
2java
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.List;
6
7public class Solution {
8    List<List<Integer>> ans;
9    List<Integer>[] graph;
10    int[] rank; 
11    int globalRank = 0; 
12
13    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections){
14        ans = new ArrayList<List<Integer>>();
15        graph = new ArrayList[n];
16        rank = new int[n];
17        Arrays.fill(rank,-2); 
18
19        // Build adjacency list
20        for(int i = 0; i < n; i++){
21            graph[i] = new ArrayList<>();
22        }
23        for(List<Integer> edge : connections){
24            graph[edge.get(0)].add(edge.get(1));
25            graph[edge.get(1)].add(edge.get(0));
26        }
27
28        dfs(0,-1);
29        return ans;
30    }
31
32    public int dfs(int node, int parent){
33        rank[node] = this.globalRank;
34        this.globalRank++;
35        int minRank = this.globalRank;
36
37        for(int neighbor : this.graph[node]){
38            if (neighbor == parent){
39                continue;
40            }
41            if (rank[neighbor] == -2){
42                minRank = Math.min(minRank, dfs(neighbor, node));
43                if (this.globalRank < rank[neighbor]) {
44                    ArrayList<Integer> temp = new ArrayList<>();
45                    temp.add(node);
46                    temp.add(neighbor);
47                    ans.add(temp);
48                }
49            } else {
50                minRank = Math.min(minRank, rank[neighbor]);
51            }
52        }
53        return minRank;
54    }
55}

In the Java solution, similar to the Python solution, we use DFS to search the graph to find all critical connections. However, for convenience, we use ArrayLists and Arrays to replace defaultdicts and normal lists.