Leet Code: 1192. Critical Connections in a Network [Hard]
Problem link: https://leetcode.com/problems/critical-connections-in-a-network/
Problem Description:
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network 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 server.
Return all critical connections in the network in any order.
The problem essentially wants us to find the bridges in the graph.
Initial and simple approach:
Remove each edge one by one and see if removing an edge increases the number of components in the graphs. If so, then it is a critical connection else it isn’t. The time complexity of such a solution will be O(E(V+E))
Efficient Approach :
The idea is that for a particular vertex, if there is no back-edge from its subgraph to the vertex’s parent or ancestor, then the edge is a critical connection(a bridge). The Time complexity of this approach is O(V+E).
If there is now back edge in a vertex sub-graph then low_time(child) will be greater than discovery_time(parent).
Code:
