# 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 **G** – **n** (**1≤ n≤ 3000**).
The rest of file consists of **n** lines. Each line starts with a number **k _{i}** (

**0≤ k**), followed by

_{i}≤ 20**k**different numbers of vertices

_{i}**l**such that there is an edge following from

_{(i, j)}**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 **t _{j}**, followed by

**t**numbers of vertices in

_{j}**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.in | strongly.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

Printable version