Hello everyone !!
Recently I was learning the Kosaraju's Algorithm for finding SCC's and after having learnt about it, I was wondering if we could traverse the transpose of the graph without actually reversing the edges (i.e., creating a new adjacency matrix). I couldn't come up with any solution so can anyone share their thoughts on how it can be done ?
You can reverse the topological sort instead
I.m sorry, I don't see what we will be accomplishing by doing that. In Kosaraju's algorithm, we have to traverse over the transpose of the graph.
If I am missing something, please correct me.
If you don't want to create two adjacency lists you can use Tarjan's algorithm instead, which finds SCCs with just one DFS.
Thank you. I didn't knew there existed a simpler algorithm for SCC's.
Build double edges and mark if its reserved edge or not, look at this:
or you can build two graphs: