# DFS on reversed graph

I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.

While I see this happening with an adjacency matrix representation(the reverse is the matrix transpose, and you can determine its elements on demand), I'm having a hard time coming up with a solution in the case of the adjacency list representation.

Any hints?

• What does "walking the edges in reverse fashion" mean? – Yuval Filmus Sep 7 '18 at 7:07
• Traverse the edge – Radu Stoenescu Sep 7 '18 at 7:28
• you can create a new adjacency list representing the reverse of all edges in O(e) time. Trivially – ratchet freak Sep 7 '18 at 9:17

You can iterate over all of the edges in $O(|E|)$ time. So, construct a copy of the graph with reversed edges as follows: iterate over all the edges, and as you examine each edge, add the reversed edge to the copy. That takes $O(|E|)$ time in total, and you only need to do it once, as a pre-processing step. Now, during Kosaraju's algorithm, if you ever need to walk edges in a reversed fashion, you can just refer to the reversed graph you created earlier.