### dgupta0812's blog

By dgupta0812, history, 3 years ago,

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 ?

• +11

 » 3 years ago, # |   0 You can reverse the topological sort instead
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +4 If you don't want to create two adjacency lists you can use Tarjan's algorithm instead, which finds SCCs with just one DFS.
•  » » 3 years ago, # ^ |   0 Thank you. I didn't knew there existed a simpler algorithm for SCC's.
 » 3 years ago, # | ← Rev. 2 →   0 Build double edges and mark if its reserved edge or not, look at this: define a graph: vector > adj[MAXN]; addedge u->v: adj[u].push_back(make_pair(v, 0)) adj[v].push_back(make_pair(u, 1)) go through edges from u: for(auto v : adj[u]) { if(v.second == 0) { //original edge } else { //reserved edge } } or you can build two graphs: define: vector org[MAXN], rev[MAXN]; addedge u->v org[u].push_back(u); rev[v].push_back(v); go through original edges out of u: for(int v : org[u]) { } go through reversed edges out of u: for(int v : rev[u]) { }