search

cheran-senthil / PyRival

⚡ Competitive Programming Library
https://pyrival.readthedocs.io/
Apache License 2.0
1.15k stars 311 forks source link

'dfs' in scc is bfs #59

Closed nskybytskyi closed 3 years ago

nskybytskyi commented 3 years ago

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 3 years ago

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 3 years ago

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.