# 1192 Critical Connections in a Network

There are `n` servers numbered from 0 to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between servers `ai` and `bi`. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

``````             2
/ |
1   |
critical | \ |
|   0
3

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
``````

Example 2:

``````Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
``````

Constraints:

• `2 <= n <= 105`
• `n - 1 <= connections.length <= 105`
• `0 <= ai, bi <= n - 1`
• `ai != bi`
• There are no repeated connections.
 `````` 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: rank = {} graph = defaultdict(list) conn_dict = {} def criticalConnections( self, n: int, connections: List[List[int]] ) -> List[List[int]]: self.formGraph(n, connections) self.dfs(0, 0) return [[u, v] for u, v in self.conn_dict] def dfs(self, node: int, discovery_rank: int) -> int: # node is already visited if self.rank[node]: return self.rank[node] # Update rank self.rank[node] = discovery_rank # This is the max we have seen till now. # So we start with this instead of INT_MAX or something. min_rank = discovery_rank + 1 for neighbor in self.graph[node]: # Skip the parent. if self.rank[neighbor] and self.rank[neighbor] == discovery_rank - 1: continue recursive_rank = self.dfs(neighbor, discovery_rank + 1) # Step 1, check if this edge needs to be discarded. if recursive_rank <= discovery_rank: del self.conn_dict[(min(node, neighbor), max(node, neighbor))] # Step 2, update the minRank if needed. min_rank = min(min_rank, recursive_rank) return min_rank def formGraph(self, n: int, connections: List[List[int]]): # Reinitialize for each test case self.rank = {} self.graph = defaultdict(list) self.conn_dict = {} # Default rank for unvisited nodes is "null" for i in range(n): self.rank[i] = None for edge in connections: # Bidirectional edges. u, v = edge, edge self.graph[u].append(v) self.graph[v].append(u) self.conn_dict[(min(u, v), max(u, v))] = 1``````