0048. Strongly connected components

Input file name: strongly.in
Output file name: strongly.out
Time limit: 1 s
Memory limit: 64 megabytes

Strongly connected component of the (directed) graph G is a subgraph G' such that for each pair of vertices a, b from G' there is a path in G' from a to b and from b to a also, and there is no set of vertices of G which can be added to G' leaving this condition true. Your task is to find all strongly connected components for a given graph G.

Input file

The first line of the input file contains number of vertices in Gn (1≤ n≤ 3000). The rest of file consists of n lines. Each line starts with a number ki (0≤ ki≤ 20), followed by ki different numbers of vertices l(i, j) such that there is an edge following from i to l(i, j).

Output file

The first line of the output file is the number of components L. The next L lines are in following format. They start each with a number tj, followed by tj numbers of vertices in j-th component. Vertices in each component are to be displayed in ascending order. Components are to be output in ascending order by minimal vertex number. All numbers inside one line are separated by one space.

Examples:

strongly.instrongly.out
3 2 2 3 1 1 0 2 2 1 2 1 3


Source: Petrozavodsk training camp, Summer 2002. Conclusive contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution