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: