Grokking Graph Algorithms for Coding Interviews

0% completed

​

Critical Connections in a Network (hard)

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:

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Ahmad Khatib

· a year ago

Take the first example, if we respect the diagram, the answer should include edges [2,3] because 3 would not be reachable by any node and [3,4] because then node 3 cannot reach node 4. Right?

Show 1 reply