I don't understand the core of Kosaraju's algorithm. From what I understand, the results should depend on how you order the nodes before doing the first DFS step. Maybe I didn't understand the pseudocode from Wikipedia correctly. See example below.
Can you explain how Kosaraju's algorithm works on this graph?
A --> B
I should get two distinct components since there is no way to get from B to A. However, if I start the DFS in A, the stack becomes [A, B]. Then we pop B, we assign B to the component with root B and because A points to B, A is also added to the component of B.
This makes no sense to me.
What did I do wrong?
You should add nodes to the stack after completing the DFS search, so you add B and then A. Therefore, the first node you pop is A, which has no nodes pointing to it, so it becomes its own component. Starting the search on N yields the same result.
P.D. Sorry for posting such an obvious question but I spent a lot of time without coming up with an answer and no one seemed to have had the same issue. I realized my dumb mistake shortly after. I'll just leave it up, answer it and close it myself in hopes of helping someone else in the future.