Problem statement

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

Solution

In my opinion it is very difficult problem if you are not familiar with graph theory. What is actually asked here is to find all so-called bridges in given graph, here you can see detailed explanation of the very classical algorithm: https://cp-algorithms.com/graph/bridge-searching.html

Here I give some details about the code, using the link I provided. The key observation about the bridge is:

Let us be at node when we use dfs. Then if we have edge (node, child), such that from child or any of its descendants we do not have back edge (edge which leads to already visited node) to node or to some of its ancestors, it means that (node, child) is bridge. Indeed, this condition means that there is only one path from node to child.

  1. We use dfs with some extra steps to solve this problem. Each time we run dfs(node, par), where node is current node we are in and par is parent of this node. In the beginning par is equal to -1 means, that we do not have any parent.
  2. We keep global self.timer variable: is time of visit of one or another node.
  3. We keep tin[node] array, the time when we visit node.
  4. Also we keep fup[node] array, which will be defined as follow: it is minimum among tin[node]: time of visit of node and all times of visit for so-called back edges and fup[child] for all children of node. By our definition, fup[node] is the smallest time among all descendants of node.

Then it can be shown that (node, child) is bridge if and only if fup[child] > tin[node].

Complexity

Time complexity is just O(E + V) to traverse all graph with dfs and some extra-steps. Space complexity is O(E + V) as well to create graph and keep used, tin, fup arrays.

Code

class Solution:
    def criticalConnections(self, n, connections):
        used, tin, fup = [0]*n, [-1]*n, [-1]*n
        self.timer, ans = 0, []
        graph = defaultdict(list)
        
        def dfs(node, par = -1):
            used[node] = 1
            tin[node] = fup[node] = self.timer + 1
            self.timer += 1
            for child in graph[node]:
                if child == par: continue
                if used[child] == 1:
                    fup[node] = min(fup[node], tin[child])
                else:
                    dfs(child, node)
                    fup[node] = min(fup[node], fup[child])
                    if fup[child] > tin[node]: ans.append([node, child])
        
        for i, j in connections:
            graph[i].append(j)
            graph[j].append(i)
            
        for i in range(n):
            if not used[i]: dfs(i)
                
        return ans