4 ms·
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 mislabe
by spankalee 1y ago
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.
- emih 1y agoWhoops, 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.
- spankalee 1y agoNice. 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...