Grokking Graph Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Critical Connections in a Network

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!
Jakhongir Rasulov

Jakhongir Rasulov

· 2 years ago

I've discovered that Tarjan's algorithm is used to solve this problem. But, unfortunately, I've not been able to wrap my head around this algorithm well enough.

Does anybody know a good idea of "getting" this algorithm?

Reading Progress

0%