Leetcode 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 = 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 = [,,,]
Output: []
Explanation: [] is also accepted.
Constraints:
1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections != connections
There are no repeated connections.
class Solution:
def criticalConnections(self, n: int, connections: List]) -> List]:
graph = [[] for _ in range(n)]
visitedTime =
lowTime =
visited =
result = []
time = 0
for connection in connections:
first = connection
second = connection
graph.append(second)
graph.append(first)
def dfs(curt: int, parent: int):
nonlocal time
visited = True
visitedTime = lowTime = time
time += 1
for neighbor in graph:
if neighbor == parent: continue
if not visited:
dfs(neighbor, curt)
lowTime = min(lowTime, lowTime)
if visitedTime < lowTime:
result.append()
else:
lowTime = min(lowTime, visitedTime)
dfs(0, -1)
return result
页:
[1]