5 ms·
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 b
by spankalee 1y ago
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.
- emih 1y agoThat 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...