SCC in linear time

This is about computing strongly connected components in a directed graph. It is well-known that two DFS can do it in linear time.

The idea is to look at the DAG with each SCC collapsed into one node. Now if we do a DFS and if somehow we can start with a component with no outgoing edge, then we are good because all reachable nodes are in the same component. To this end we can do a DFS and we know that components finished last has no incoming edges. Why, an incoming edge cannot come from its ancestor because ancestors always finish after their descendants. This excludes tree edges and forward edges. The incoming edge cannot be a back edge because then the ancestor and descendant will be in the same component. So it can only be a cross edge from right to left. But then a component in the left always finishes before a right one so this cannot happen.

To conclude, a component finished last cannot have incoming edges. In particular, the component containing the root of the DFS tree finished last. Now if we reverse all the edges, then the component finished last does NOT have outgoing edges and every node in the same component is still reachable from each other. Put it another way, G and G(rev) has the same SCC. Now we just go through each node in reverse order of finish time and do a DFS to collect all nodes in the same component.