Critical Connections in a Network
Understanding the Problem
We are given an undirected graph of servers and connections. We need to find all "bridges" in this graph, meaning edges whose removal would disconnect the graph (or at least disconnect some part of it from another).
A road network is a useful analogy. Most cities have multiple routes between them, but sometimes a single road connects two regions. If that road closes, the regions become isolated. A critical connection is that single road.
Checking each edge independently, by removing it and running a connectivity check, is too slow at this input size. Tarjan's bridge-finding algorithm finds every bridge in a single DFS by tracking discovery times and low-link values.
An edge (u, v) is a bridge if and only if no back edge from the subtree rooted at v (in the DFS tree) reaches u or any ancestor of u. When no such back edge exists, the edge (u, v) is the only link between v's subtree and the rest of the graph.
Key Constraints:
2 <= n <= 10^5: with up to 100,000 nodes, the algorithm must be linear or near-linear. O(n^2) is about 10^10 operations, far beyond what runs in time.n - 1 <= connections.length <= 10^5: the graph is sparse, and the lower bound of n - 1 edges means it is connected (it contains at least a spanning tree).- No repeated connections and no self-loops: the graph is simple. This matters in Approach 2, where the parent check relies on there being at most one edge between any two nodes.
Approach 1: Brute Force (Remove Each Edge)
Intuition
The definition of a bridge can be tested directly: remove an edge (u, v) and check whether u can still reach v through the rest of the graph. If u can no longer reach v, then that edge was the only path between them, so it is a critical connection. We repeat this test for every edge.
Checking reachability between the two endpoints is more reliable than counting how many nodes are reachable from a fixed start node. A node that is never mentioned in the connections list stays isolated regardless of which edge we remove, so a global count would always fall short and wrongly flag every edge.
Algorithm
- Build an adjacency list from the connections.
- For each edge (u, v) in the connections list:
- Temporarily remove the edge (u, v) from the adjacency list.
- Run BFS or DFS starting from u and check whether v is reachable.
- If v is not reachable, the edge is a bridge. Add it to the result.
- Restore the edge.
- Return all identified bridges.
Example Walkthrough
Code
- Time Complexity: O(E * (V + E)). For each of the E edges, we rebuild the adjacency list in O(E) and run BFS in O(V + E). With V and E both up to 10^5, this is roughly 10^10 operations, far too slow.
- Space Complexity: O(V + E). The adjacency list and visited array for each iteration.
This approach is correct but repeats a full graph rebuild and BFS for every edge. Tarjan's algorithm finds all bridges in one DFS traversal.
Approach 2: Tarjan's Bridge-Finding Algorithm (Optimal)
Intuition
Running DFS on a connected undirected graph produces a DFS tree, and every edge of the original graph falls into one of two categories:
- Tree edges - edges that are part of the DFS tree (the edges traversed to discover new nodes).
- Back edges - edges that connect a node to an already-visited ancestor in the DFS tree.
Back edges are important because they create cycles. If there is a back edge from some node in v's subtree to u or an ancestor of u, then even if we remove the tree edge (u, v), we can still reach v's subtree through the back edge. But if no such back edge exists, removing (u, v) disconnects v's subtree from the rest of the graph, making (u, v) a bridge.
To detect this during the traversal, assign each node two values:
- disc[v] (discovery time): the order in which DFS first visits node v.
- low[v] (low-link value): the minimum discovery time reachable from v's subtree, considering both tree edges and back edges.
The low-link value captures the "earliest ancestor" that v's subtree can reach via a back edge. If low[v] > disc[u], it means v's subtree cannot reach u or any ancestor of u through any path other than the edge (u, v). So (u, v) is a bridge.
DFS on an undirected graph produces no cross edges: every non-tree edge connects a node to one of its ancestors. This is what makes the two-category split (tree edge or back edge) exhaustive, and it is the property that fails for directed graphs.
An edge is a bridge if and only if it lies on no cycle. A back edge from v's subtree to u or above closes a cycle through the tree edge (u, v), and low[v] <= disc[u] holds precisely when such a back edge exists. The test low[v] > disc[u] therefore flags exactly the edges that lie on no cycle.
Algorithm
- Build an adjacency list from the connections.
- Initialize arrays
discandlowof size n, filled with -1 (unvisited). - Start DFS from node 0 with parent -1 and a global timer starting at 0.
- For each node u during DFS:
- Set
disc[u] = low[u] = timer++. - For each neighbor v of u:
- If v is the parent of u in the DFS tree, skip it.
- If v is unvisited, recurse into v with parent u. After returning, update
low[u] = min(low[u], low[v]). Iflow[v] > disc[u], add edge (u, v) to the result. - If v is already visited (and is not the parent), it is a back edge. Update
low[u] = min(low[u], disc[v]). - Return the collected bridges.
Skipping the parent by node id in step 4 is safe only because the problem guarantees no repeated connections. If parallel edges were allowed, a second (u, v) edge would itself be an alternative path between u and v, and the skip would have to compare edge ids instead of node ids.
Example Walkthrough
Code
- Time Complexity: O(V + E). We visit each node exactly once and examine each edge exactly twice (once from each endpoint). Building the adjacency list takes O(E). The entire algorithm runs in linear time.
- Space Complexity: O(V + E). The adjacency list takes O(V + E). The disc and low arrays take O(V). The recursion stack in the worst case (a line graph) goes O(V) deep.