Skip to main content
Talentd

Critical Connections in a Network - Solution & Explanation

HardDepth-First SearchGraphBiconnected Component19 min readAsked at: Amazon, Microsoft, ServiceNow +5
Practice this problem

Problem Statement

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

 

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

 

Constraints:

  • 2 <= n <= 105
  • n - 1 <= connections.length <= 105
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • There are no repeated connections.

Approach Overview

Problem Overview: You are given n servers connected by bidirectional edges. A connection is critical if removing it disconnects part of the network. The task is to return all such edges, also known as bridges in graph theory.

Approach 1: Edge Removal + Connectivity Check (Brute Force) (Time: O(E * (V + E)), Space: O(V + E))

Remove each edge one at a time and run a DFS or BFS to check whether the graph is still fully connected. If the number of reachable nodes decreases, that edge is a critical connection. Implementation is straightforward: build the adjacency list, temporarily skip the tested edge, then run a traversal from any node. This approach works for small graphs but becomes expensive because you repeat a full traversal for every edge.

Approach 2: Union-Find Connectivity Testing (Time: O(EĀ² Ī±(V)), Space: O(V))

Another option rebuilds connectivity using a Union-Find structure for each edge exclusion. For every edge (u, v), rebuild the disjoint set using all other edges and check whether u and v remain connected. Path compression and union by rank make each union nearly constant time, but rebuilding the structure repeatedly still leads to quadratic behavior. This approach helps demonstrate connectivity reasoning but is rarely the optimal bridge detection method.

Approach 3: DFS with Tarjan's Algorithm (Optimal) (Time: O(V + E), Space: O(V))

The optimal solution uses a single Depth-First Search traversal combined with Tarjan's bridge-finding technique. Each node records two values: its discovery time and the lowest discovery time reachable through its subtree (low). While exploring neighbors, update the low-link values using back edges. If for an edge (u, v) the condition low[v] > disc[u] holds, there is no alternative path from v back to u or its ancestors, meaning the edge is a bridge. This method processes every vertex and edge exactly once, making it linear time. It is a standard technique in graph problems involving bridges and biconnected components.

Recommended for interviews: Interviewers expect the Tarjan DFS solution because it demonstrates strong graph fundamentals and understanding of bridge detection. Mentioning the brute force edge-removal idea first shows problem intuition, but implementing the linear-time Tarjan approach signals deeper algorithmic skill.

Approach 1: Depth-First Search (DFS) and Tarjan's Algorithm

This approach leverages Tarjan's Algorithm to find bridges in an undirected graph. A bridge, also known as a critical connection, is an edge which, when removed, increases the number of connected components in a graph.

The main idea is to use a DFS traversal while keeping track of two things for each node:

  • Discovery time: The time when a node is first visited.
  • Lowest point: The smallest discovery time reachable from the node, including itself or its descendants.

During the DFS traversal, if a node discovers a node that was discovered earlier, we update the current node's lowest point based on the discovered node unless it is a direct parent of the current node which means it's a backtracking edge. If the lowest point of the descendant is greater than the discovery time of the current node, then the connection between them is a critical connection.

The code defines a function criticalConnections which constructs a graph from the given connections. It uses DFS traversal to calculate the disc and low values. The critical connections are collected in critical_edges list.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack.

Try this approach in the editor ā†’

Approach 2: Union-Find with Path Compression

The Union-Find approach is less direct for this problem as it better suits static connectivity queries, but it can verify the disconnection effect of removing an edge by checking connectivity before and after its removal.

Here, a variation of Kruskal's algorithm can be employed with additional tracking to retry connections and verify their critical status. However, this requires additional complexity and is not the standard usage for critical connections.

So, while possible, using Union-Find isn't recommended due to its inefficiency in recomputing components with high time complexity.

The code implements a brute-force check of each edge's removal effect by rebuilding a Union-Find structure for each remaining connection set. It provides an intuitive understanding though not efficient for large inputs.

Code

PythonC++

Python

C++

Complexity

The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure.

Try this approach in the editor ā†’

Approach 3: Tarjan Algorithm

The "critical connections" in this problem can be considered as "bridges".

"Bridges": In a connected undirected graph, if removing a certain edge makes the graph disconnected, then this edge can be considered as a "bridge".

Correspondingly, there is also the concept of "articulation points".

"Articulation Points": In a connected undirected graph, if removing a certain point and all edges connected to it makes the graph disconnected, then this point can be considered as an "articulation point".

There is an algorithm called the Tarjan algorithm for finding "bridges" and "articulation points" in a graph. This algorithm uses a depth-first search (DFS) method that first recursively visits adjacent nodes and then visits the node itself. By recording the "order of visit: DFN" and updating the "earliest backtrackable node: low" when visiting the node itself after recursion ends, it can find the "bridges" and "articulation points" of the graph in O(n) time. Also, this algorithm can be used to find strongly connected components in directed graphs.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS) and Tarjan's Algorithm

The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is also O(V + E) due to the graph representation and recursion stack.

Union-Find with Path Compression

The time complexity on worst-case is O(E^2) due to the need for reconstructing the Union-Find structure. The space complexity is O(V) for the Union-Find structure.

Tarjan Algorithmā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Edge Removal + DFS/BFSO(E * (V + E))O(V + E)Conceptual brute force approach for understanding bridges
Union-Find Rebuild per EdgeO(EĀ² Ī±(V))O(V)When experimenting with connectivity structures like disjoint sets
DFS with Tarjan's AlgorithmO(V + E)O(V)Optimal solution for detecting bridges in undirected graphs

Video Solution

Critical Connections In a Network | Tarjans Algorithm for Bridge Detection | Leetcode 1192 ā€¢ Tech Revisions ā€¢ 42,917 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Critical Connections in a Network easy or hard?
The problem is rated Hard on LeetCode because it requires understanding Tarjan's algorithm and low-link values. While the DFS traversal itself is straightforward, correctly maintaining discovery times and detecting bridges requires solid graph theory knowledge.
Critical Connections in a Network Python/Java solution
Most implementations use Tarjan's DFS algorithm with adjacency lists. The same logic works across Python, Java, C++, and JavaScript: track discovery time, maintain low values, and record edges where low[v] > disc[u]. This produces all bridges in O(V + E) time.
How to solve Critical Connections in a Network in O(n)?
Solve it with Tarjan's bridge-finding algorithm. Run a DFS while storing discovery times and low-link values for every node. When exploring an edge (u, v), if low[v] becomes greater than disc[u], that edge is a bridge. This processes all vertices and edges once, giving O(V + E) complexity.
What is the best approach for Critical Connections in a Network?
The best approach uses Tarjan's Algorithm with a Depth-First Search. It tracks discovery time and low-link values for each node to identify bridge edges. If low[v] > disc[u], the edge (u, v) is a critical connection. This algorithm runs in O(V + E) time and processes each node and edge once.
Is Critical Connections in a Network asked at Google/Amazon/Meta?
Critical bridge detection problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test deep graph knowledge. Variations often require detecting bridges, articulation points, or biconnected components using DFS-based algorithms.
What data structure is used in Critical Connections in a Network?
The core data structure is an adjacency list representing the graph. The algorithm also uses arrays or lists to store discovery times, low-link values, and visited states during DFS. Some alternative implementations experiment with Union-Find structures for connectivity checks.
What is the time complexity of Critical Connections in a Network?
The optimal Tarjan DFS solution runs in O(V + E) time with O(V) space. Each node is visited once and each edge is examined during the DFS traversal. Brute force approaches that remove edges and recheck connectivity can take O(E * (V + E)) time.

Ready to solve this problem?

Practice Critical Connections in a Network with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree