Graph transpose ($G^T$)

The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.