By what factor is Kosaraju's algorithm for finding strongly connected component slower as compared to Tarjan's algorithm. It appears to me that the factor should be 3 as there are 2 dfs passes in Kosaraju's algorithm and we also have to transpose the graph once. Am I missing something ?
Also is there any way to find the tranpose graph without declaring a new graph and storing the edges in reverse order ? (Basically reversal of graph without use of extra memory)
If in original graph you have edges as sorted adjacency list, to find the transpose edges you just go int next from (|V|-1 to 0], and have a pointer to last edge in adjacency list. If it's same as pointer, you decrease the pointer, if not, you know it's a transpose edge.