Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Critical Connections in a Network (hard)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

You are given n servers numbered from 0 to n-1, connected by some number of undirected connections 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 servers.

Return all critical connections in the network.

Examples

Example 1:

  • Input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]]
  • Expected Output: [[1,2],[0,1]]
Image
  • Justification: Removing either [0, 1] or [1, 2] will split the network into separate parts, making some servers unreachable from others.

Example 2:

  • Input: n = 4, connections = [[0, 1], [0, 2], [1, 2], [2, 3]]
  • Expected Output: [[2, 3]]
Image
  • Justification: Removing [2, 3] will isolate server 3, making it unreachable from the other servers.

Example 3:

  • Input: n = 6, connections = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
  • Expected Output: [[1, 3]]
Image
  • Justification: Removing [1, 3] will disconnect servers 3, 4, and 5 from the rest of the network.

Constraints:

  • 2 <= n <= 10<sup>5</sup>
  • n - 1 <= connections.length <= 10<sup>5</sup>
  • 0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1
  • a<sub>i</sub> != b<sub>i</sub>
  • There are no repeated connections.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself