Module: Componentes fuertemente conectados y condensación de gráficos


Problem

1 /1


Buscar componentes fuertemente conectados

Problem

Tienes un gráfico dirigido con N vértices y M aristas (1<=N<=20000, 1<=M<=200000). Encuentre los componentes fuertemente conectados del gráfico dado y ordene topológicamente su condensación.
 
Entrada
El gráfico se proporciona en el archivo de entrada de la siguiente manera: la primera línea contiene los números N y M. Cada una de las M líneas siguientes contiene una descripción del borde — dos números enteros de 1 a N — números de inicio y fin de borde.
 
Salida
En la primera línea, escriba el número K — el número de componentes fuertemente conectados en un gráfico dado. En la siguiente línea, escriba N números — para cada vértice imprime el número de la componente fuertemente conexa a la que pertenece este vértice. Los componentes fuertemente conectados deben numerarse de tal manera que para cualquier borde el número del componente fuertemente conectado de su principio no exceda el número del componente fuertemente conectado de su final.

Entrar Salida
10 19
14
78
5 10
8 9
96
26
6 2
38
9 2
7 2
97
4 5
36
73
6 7
108
10 1
29
27
2
1 2 2 1 1 2 2 2 2 1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!