The running time is O(|V|+|E|).
If u and v are in the same component, then there is a path from u to v. If u and v are in different component, since the component graph is a linear chain. There is one path from u to v or v to u.
We can reduce the subgraph in one component to a cycle. Then this graph has the same component graph and has fewest edges.
In the SCC’s algorithm, we can compute the component’s numbering. Then we can find all edges which endpoints are in different components. These edges are the edges in the component graph. But the graph is not simple graph, we must transform it into simple graph.
G’s transpose’s component graph, is G’s component graph’s transpose. Hence they are equivalent.
Incorrect. Let G=(V,E), V={0,1,2}, E={<0,1>,<0,2>,<1,0>}. If we start DFS with node 0, then the result is incorrect.
It may decrease by at most |V|-1 component. Thinking about a directed path with |V| nodes, the number of components is |V|. If we add a edge that the graph becomes a cycle, then the number of components is 1.
