Strongly Connected Components
Time limit2sMemory limit128 MB
Compute all strongly connected components of a directed graph with up to 10,000 vertices and 100,000 edges, printing each component sorted, ordered by its smallest vertex.
Problem
Given a directed graph, write a program that divides the graph into its strongly connected components.
A strongly connected component is a maximal set of vertices such that, for any two distinct vertices u and v in the set, there is a path from u to v and also a path from v to u.
A component may contain only one vertex. Such a single-vertex component does not require a self-loop.
Input
The first line contains two integers V (1 <= V <= 10,000) and E (1 <= E <= 100,000), the number of vertices and edges in the graph.
Each of the next E lines contains two integers A and B, meaning there is a directed edge from vertex A to vertex B.
The vertices are numbered from 1 to V.
Output
Print the number K of strongly connected components on the first line.
Then print K lines, one for each component. On each line, print the vertices in that component in increasing order, followed by -1 to mark the end of the line.
Print the components in increasing order of the smallest vertex contained in each component.