Graph Theory37 sections · 1633 units
Open in Course

Low-Link Intuition

(Can you escape the subtree?)

Think of low[v] as how far back you can reach from vv using the edges in your subtree. If low[v] < disc[v], then there is a back edge from the subtree of vv to an ancestor. This back edge provides an alternate path, preventing bridges.

If low[v] = disc[v], then the subtree of vv is a dead end with no back edges escaping. The edge from the parent to vv is critical because it is the only connection.