'dfs' in scc is bfs
nskybytskyi opened this issue · 2 comments
nskybytskyi commented
lines 33 and 34 in /graphs/scc.py should be a dfs, but are bfs in this order, pls swap. in particular, scc([[1, 2], [2], []])[0] = [0, 0, 1] , expected [0, 1, 2]
nskybytskyi commented
actually, no, swapping them won't help, in the new version scc([[1], [2], [0]])[0] = [0, 1, 0], so it is broken in an even worse way
bjorn-martinsson commented
That implementation is known to be buggy, and we've had a PR "Added a working SCC" fixing it since some while ago. I'll merge it later today.