1192. Critical Connections in a Network

[LLancelot]

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.

[LLancelot]

代码

class Solution(object):
    def criticalConnections(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: List[List[int]]
        """
        g = collections.defaultdict(set)
        for u, v in connections:
            g[u].add(v)
            g[v].add(u)
        
        jump = [-1] * n
        
        def dfs(v, parent, level, jump, res, g):
            
            jump[v] = level + 1
            
            for child in g[v]:
                
                if child == parent:
                    continue
                
                elif jump[child] == -1:
                    # unvisited node, do dfs
                    jump[v] = min(jump[v], dfs(child, v, level + 1, jump, res, g))
                
                else:
                    jump[v] = min(jump[v], jump[child])
                    
            if jump[v] == level + 1 and v != 0:
                # this is a critical connection
                res.append([parent, v])
            
            return jump[v] 
        
        
        # main
        res = []
        dfs(0, -1, 0, jump, res, g)
        return res