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.

Accepted 93,286 Submissions 186,676

First thought that came to my mind was to do a node discovery runs on each of the nodes. The search will give a list of redundant path, which we can use to determine non-critical connections. Repeat this for n nodes, and pick the connections that are not non-critical.

Glad it was the first thought and not the solution! Because it is convoluted and I’m not even sure if it will yield the desired output.

Now, the second thought is to iterate over the connections array. Since we are to find whether the given connection is critical, we can try removing that connection from the graph and test if the reachability is still the same.

For this we can run a graph searching algorithm - BFS/DFS/etc - from either of the nodes that the deleted connection contains. If we find the other node from the search, then the reachability is still the same. This is due to the fact that, however convoluted, any path that utilized the deleted connection now can use the newly found path between the two nodes.

Todo:

• Complexity calculation