Problem statement

https://binarysearch.com/problems/Edges-that-Disconnect-the-Graph/

Solution

The same as Leetcode 1192. Critical Connections in a Network

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 solve(self, graph):
        n = len(graph)
        used, tin, fup = [0]*n, [-1]*n, [-1]*n
        self.timer, ans = 0, []
        
        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 in range(n):
            if not used[i]: dfs(i)
                
        return len(ans)