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 <= 105n - 1 <= connections.length <= 1050 <= ai, bi <= n - 1ai != biThe key idea behind #1192 Critical Connections in a Network is to identify bridges in an undirected graph. A bridge is an edge whose removal increases the number of connected components in the network. In graph theory, this can be efficiently solved using a Depth-First Search (DFS) based algorithm commonly known as Tarjan’s Algorithm.
During DFS traversal, we assign each node a discovery time and track the earliest reachable discovery time using a low[] array. If a neighbor cannot reach an ancestor of the current node through a back edge, the edge connecting them is considered a critical connection. The algorithm keeps updating discovery and low-link values while exploring neighbors.
By using adjacency lists and a single DFS traversal, all bridges can be detected efficiently. This approach is optimal because each node and edge is processed once, making it well-suited for large network graphs commonly seen in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Tarjan's Bridge Algorithm | O(V + E) | O(V + E) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use 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:
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 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.
1def criticalConnections(n, connections):
2 from collections import defaultdict
3 graph = defaultdict(list)
4 for u, v in
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.
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 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.
1class UnionFind:
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, bridge detection and Tarjan's Algorithm are common graph interview topics at FAANG-level companies. Problems like this test a candidate's understanding of DFS, graph traversal, and advanced graph concepts such as biconnected components.
The optimal approach uses Tarjan's Algorithm with Depth-First Search to detect bridges in a graph. By tracking discovery times and low-link values, the algorithm determines whether an edge is critical. This allows all bridges to be found in linear time.
Low-link values represent the earliest discovery time reachable from a node through DFS, including back edges. They help determine whether a subtree can reconnect to an ancestor, which is essential for identifying bridges.
An adjacency list is the most efficient data structure for representing the graph in this problem. It allows fast traversal of neighbors during DFS and keeps memory usage efficient for sparse graphs.
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.