Leetcode 1300 Solution

This article provides solution to leetcode question 1300 (critical-connections-in-a-network)
Categories:
Tags:
Access this page by simply typing in "lcs 1300" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/critical-connections-in-a-network

Solution

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = collections.defaultdict(set)
        for src, dst in connections:
            graph[src].add(dst)
            graph[dst].add(src)



        non_critical_connections = set()
        def add_node(src, dst):
            small = min(src, dst)
            big = max(src, dst)
            non_critical_connections.add((small, big))



        visited = [None] * n



        def dfs(node, src, step=0):
            nonlocal visited



            if visited[node] is not None:
                return visited[node]



            visited[node] = step



            child_min_step = step
            for neigh_node in graph[node]:
                if neigh_node == src:
                    continue



                child_step = dfs(neigh_node, node, step + 1)
                child_min_step = min(child_min_step, child_step)



                if child_step <= step:
                    add_node(node, neigh_node)



            return min(step, child_min_step)



        dfs(0, None)



        ans = []
        for src, dst in connections:
            small = min(src, dst)
            big = max(src, dst)
            if (small, big) not in non_critical_connections:
                ans.append((small, big))
        return ans