This is a well known algorithm to find bridges in a graph, it is based on discovery times.
The idea is the following:
- Start a DFS from any non-visited node
- Maintain discovery time list
- Updating the low-link value
The low link value
The low link value comes from the idea that when you are doing a DFS traversal of a graph, you are building a tree (the recursion tree). From each node in the recursion tree, the lowest reachable discovery time can be:
- the one of an ancestor of the current node (not a direct ancestor)
- the one coming from a subgraph / subtree
The Tarjan algorithm is useful to solve to use LeetCode 1192 - Critical Connections in a Network where the graph is traversed building a discovery time network and a low-link.
If a child tree is reachable within a time higher than the current node, it means the current connection is critical