1192. Critical Connections in a Network
Critical Connections in a Network (LeetCode 1192) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Bridges & Articulation Points (Tarjan low-link) subpattern.
How to solve Critical Connections in a Network
Critical Connections in a Network is a Bridges and Articulation Points problem, part of Graph Traversal Patterns (DFS & BFS). Find bridges and articulation points in graphs using Tarjan's low-link algorithm.
Work towards the solution in these steps:
- Consider representing the network as a graph and explore graph traversal algorithms like DFS or BFS to analyze connections.
- Think about how removing certain edges might disconnect parts of the graph, and how to identify these edges during traversal.
- Use DFS with tracking of discovery times to understand the order in which nodes are visited and how they relate to each other.
The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.
The Critical Connections in a Network solution and editorial walks through the full approach with reference code.
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] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server 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.
Constraints:
- 1 <= n <= 10^5 - n-1 <= connections.length <= 10^5 - connections[i][0] != connections[i][1] - There are no repeated connections.
Topics and companies
Topics: Depth-first Search.
Reported in interviews at Amazon, Adobe.
How to practise Critical Connections in a Network on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.
Open Critical Connections in a Network in the code editor, or read the Critical Connections in a Network editorial for a worked solution with its approach and complexity analysis.
Where Critical Connections in a Network sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Bridges & Articulation Points (Tarjan low-link) subpattern
- The full DSA patterns sheet
Problems related to Critical Connections in a Network
Other problems that use the same Bridges & Articulation Points (Tarjan low-link) and Graph Traversal Patterns (DFS & BFS) techniques:
- Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree — Hard, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern
- Build a Matrix With Conditions — Hard, same pattern
- Bus Routes — Hard, same pattern
Critical Connections in a Network FAQ
What is the LeetCode number of Critical Connections in a Network?
Critical Connections in a Network is LeetCode problem 1192, rated Hard.
What pattern is used to solve Critical Connections in a Network?
Critical Connections in a Network is a Bridges and Articulation Points problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Bridges & Articulation Points (Tarjan low-link) subpattern.
What is the time complexity of Critical Connections in a Network?
The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.
Which companies ask Critical Connections in a Network?
Critical Connections in a Network has been reported in interviews at Amazon, Adobe.