(PYTHON)

given an adjacency list

u v

1 2

1 4

4 2

2 5

5 4

3 5

6 3

Given a directed graph G you first create the reverse graph GR in linear time.

Next, you run the undirected connected components method processing the vertices in decreasing post order (Both steps in O(|V|+|E|) time)

1. Create GR

2. Compute DFS interval on GR for each node

3. Iteratively select the next unvisited node uu with highest post(u)post(u): For each such u, use DFS on G to visit all nodes reachable from u and output this set as a connected component.