Remove components sort, Kosaraju should be O(n) #1330
Conversation
sort(component.begin(), component.end()) is linearithmic, which breaks the expected linear complexity of Kosaraju. Line is also superfluous and unnecesary.
|
I'm shocked that someone rewrote this and made the code worse... It was correct before it was updated 2 months ago. You're right that there's no need to sort. |
|
Sorry, I didn't think about that. The line should indeed be removed, but this sentence should then also be modified (e.g. by removing the word 'sorted'):
Thanks for catching this mistake! |
Modify description to match the removal of sort() in algorithm.
|
@el-sambal suggestion taken, updated the description! |
|
Has this code really been tested? The code is called strongy rather than strongly... |
|
Thanks for the pull request! Generally, the article was largely rewritten in #1307, and IMO it overall got much better than it was before. Unfortunately, I indeed missed that sorting adds unnecessary overhead in complexity, and that there is a typo in the function name. But other than that, the new code is tested to some extent in |
sort(component.begin(), component.end()) is linearithmic, which breaks the expected linear complexity of Kosaraju. Line is also superfluous and unnecesary.