Leetcode 1192. Critical Connections in a Network

Seawolf

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

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

Return all critical connections in the network in any order.



Example 1:



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


Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.

1. class Solution:
   
2.     def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
   
3.         graph = [[] for _ in range(n)]
   
4.         visitedTime = [0 for _ in range(n)]
   
5.         lowTime = [0 for _ in range(n)]
   
6.         visited = [False for _ in range(n)]
   
7.         result = []
   
8.         time = 0
   
9.         
   
10.         for connection in connections:
    
11.             first = connection[0]
    
12.             second = connection[1]
    
13.             
    
14.             graph[first].append(second)
    
15.             graph[second].append(first)
    
16.         
    
17.         
    
18.         def dfs(curt: int, parent: int):
    
19.             nonlocal time
    
20.             visited[curt] = True
    
21.             visitedTime[curt] = lowTime[curt] = time
    
22.             time += 1
    
23.             
    
24.             for neighbor in graph[curt]:
    
25.                 if neighbor == parent: continue
    
26.                     
    
27.                 if not visited[neighbor]:
    
28.                     dfs(neighbor, curt)
    
29.                     lowTime[curt] = min(lowTime[curt], lowTime[neighbor])
    
30.                     if visitedTime[curt] < lowTime[neighbor]:
    
31.                         result.append([curt, neighbor])
    
32.                 else:
    
33.                     lowTime[curt] = min(lowTime[curt], visitedTime[neighbor])
    
34.                     
    
35.         dfs(0, -1)
    
36.         return result

复制代码