Tarjan's Lowlink Algorithm

• Press T to toggle auto/manual mode
• Press the Up/Down arrow keys to change speed
• Press Press the Left/Right arrow keys to step forward/back in manual mode

Note: This algorithm only deals with undirected graphs. Directed graphs require a small adjustment.

In a DFS, if a node v was visited as an adjacent node of u, we call v the child of u and call u the parent of v. These parent-child relationships form a directed tree, which is called the DFS tree. Edges part of the DFS tree are called tree edges, while edges (u, v) that aren't are

1. Forward edges, if v is a descendant of u
2. Back edges, if v is an ancestor of u
3. Cross edges, otherwise

Undirected graphs do not have cross edges.

Additionally, for all u, we store stamp[u], the timestamp of when the node was visited. We also store low[u], the lowlink of u, which is the smallest time stamp achievable by starting from u, following any number of tree edges, followed by at most one back edge.

Tarjan's Lowlink Algorithm computes low[u] for each u in linear time using the following logic:
Initialize time = 0. Inside the DFS call of node u,

1. Mark u as visited
2. Set stamp[u] = low[u] = time
3. Increment time by 1
4. For each non-parent adjacent node v:
1. If it's already been visited, set low[u] = min(low[u], stamp[v]), decreasing low[u] if (u, v) is a back edge
2. If it hasn't been visited: Call DFS(v), then set low[u] = min(low[u], low[v]),
   possibly decreasing low[u] since (u, v) is a tree edge

A node is cut vertex or a articulation point if removing it disconnects the graph. This happens iff either

1. Node u is the root of the DFS tree (first node visited) and it has at least two children
2. Node u is not the root and there exists a child v of u such that low[v] ≥ stamp[u]

An edge (u, v) is a bridge if removing it disconnects the graph. This happens iff either

1. low[v] > stamp[u]
2. low[u] > stamp[v]