Critical Connections in a Network

The problem requires finding the critical connections in a network of servers. A connection is considered critical if removing it will disconnect some servers in the network. We can find critical connections by performing a Depth-First Search (DFS) to find the bridges in the graph.

Here’s the code to find all critical connections in the network:

 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
from collections import defaultdict

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # Build the adjacency list
        graph = defaultdict(list)
        for a, b in connections:
            graph[a].append(b)
            graph[b].append(a)

        # Initialize arrays to track the discovery time and lowest time reachable for each node
        disc = [-1] * n
        low = [-1] * n

        # List to store the result
        critical = []

        # Recursive function to perform DFS
        def dfs(node, parent, time):
            disc[node] = low[node] = time
            for neighbor in graph[node]:
                # Skip the parent node in DFS traversal
                if neighbor == parent:
                    continue
                # If the neighbor is not visited, recursively visit it
                if disc[neighbor] == -1:
                    dfs(neighbor, node, time + 1)
                # Update the lowest reachable time for the current node
                low[node] = min(low[node], low[neighbor])
                # If the lowest reachable time of neighbor is greater than discovery time of node, it's a critical connection
                if low[neighbor] > disc[node]:
                    critical.append([node, neighbor])

        # Start DFS from the first node
        dfs(0, -1, 0)

        return critical

This code first constructs a graph using an adjacency list, then applies DFS to find the bridges or critical connections. The critical connections are those where the lowest reachable time of a neighbor is strictly greater than the discovery time of the current node.

The given examples will produce the expected output:

1
2
3
4
5
6
7
n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
# Output: [[1,3]]

n = 2
connections = [[0,1]]
# Output: [[0,1]]