1192. Critical Connections in a Network - cocoder39/coco39_LC GitHub Wiki

1192. Critical Connections in a Network

starting from node 0 and setting its rank to 0. Applying DFS to traverse the graph and propagate the rank (ie increase by 1). If rank of current node is a and the rank of the next node is smaller than a, it implies that the so called "next node" has been visited before, so cycle detected

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        rank = {}
        for i in range(n):
            rank[i] = None
        
        graph = collections.defaultdict(list)
        conn_dict = set()
        for u, v in connections:
            u, v = min(u, v), max(u, v)
            graph[u].append(v)
            graph[v].append(u)
            conn_dict.add((u, v))
            
        self.dfs(rank, graph, conn_dict, 0, 0)
    
        result = []
        for u, v in conn_dict:
            result.append([u, v])
        return result
        
    def dfs(self, rank: dict, graph: dict, conn_dict: dict, node: int, cur_rank: int) -> int:
        if rank[node]:
            return rank[node]
        rank[node] = cur_rank
        
        next_rank = cur_rank + 1
        final_rank = cur_rank + 1
        for neighbor in graph[node]:
            if rank[neighbor] and rank[neighbor] == cur_rank - 1: # skip parent
                continue
                
            recurive_rank = self.dfs(rank, graph, conn_dict, neighbor, next_rank)
            if recurive_rank <= cur_rank: # cycle detected
                u, v = min(node, neighbor), max(node, neighbor)
                conn_dict.remove((u, v))
            final_rank = min(recurive_rank, final_rank)
        
        return final_rank # min rank of all the nodes visited in the recursion