There seems to be an error in the very first example.
They show (3,1) as a valid pair, but node 3 is not labeled as being in set A. Either the graph is mislabeled or the example valid pair is wrong.
There seems to be an error in the very first example.
They show (3,1) as a valid pair, but node 3 is not labeled as being in set A. Either the graph is mislabeled or the example valid pair is wrong.
Whoops, you got me. Fixed!
At some point I relabeled the vertices to match the DFS order, but I must have forgotten to update this example.
Nice. I'm liking the interactive diagrams!
I noticed another small error. Step 15 of the Tarjan's algorithm diagram reads:
> Since low[6] > 4, the edge is a bridge.
I think it should read:
> Since low[6] > low[4], the edge is a bridge.
That one is intentional. Note: a tree edge (u, v) is a bridge if and only if low[v] is strictly greater than the entry time of u.
Here 4 is the entry time of that node. (For convenience I made sure that the node labels are just the DFS entry times.)
Though maybe comparing both low values might also work, I'd have to think about that...