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 DepthFirst 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]]
