Critical Connections in a Network

Critical Connections in a Network 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.

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
• All coding practice problems

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