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.

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        visitedTime = [0 for _ in range(n)]
        lowTime = [0 for _ in range(n)]
        visited = [False for _ in range(n)]
        result = []
        time = 0
        
        for connection in connections:
            first = connection[0]
            second = connection[1]
            
            graph[first].append(second)
            graph[second].append(first)
        
        
        def dfs(curt: int, parent: int):
            nonlocal time
            visited[curt] = True
            visitedTime[curt] = lowTime[curt] = time
            time += 1
            
            for neighbor in graph[curt]:
                if neighbor == parent: continue
                    
                if not visited[neighbor]:
                    dfs(neighbor, curt)
                    lowTime[curt] = min(lowTime[curt], lowTime[neighbor])
                    if visitedTime[curt] < lowTime[neighbor]:
                        result.append([curt, neighbor])
                else:
                    lowTime[curt] = min(lowTime[curt], visitedTime[neighbor])
                    
        dfs(0, -1)
        return result