Graph Theory37 sections · 1633 units
Open in Course

Critical Connections - Core Idea

Apply Tarjan's bridge algo

The graph is undirected and connected. You need to find all bridges using Tarjan's algorithm. Run DFS, compute disc[v] and low[v] for each vertex, check each tree edge (u,v)(u, v) for the condition low[v] > disc[u].

If true, it is a bridge. Time complexity: O(V+E)O(V+E). Space complexity: O(V)O(V) for the DFS stack and arrays. This is the best solution because you must examine every edge at least once.