Module: Componentes fortemente conectados e condensação de gráficos


Problem

1 /1


Procure por componentes fortemente conectados

Problem

Você recebe um gráfico direcionado com N vértices e M arestas (1<=N<=20000, 1<=M<=200000). Encontre os componentes fortemente conectados do grafo fornecido e ordene topologicamente sua condensação.
 
Entrada
O gráfico é dado no arquivo de entrada da seguinte forma: a primeira linha contém os números N e M. Cada uma das próximas M linhas contém uma descrição da aresta — dois inteiros de 1 a N — números iniciais e finais da borda.
 
Saída
Na primeira linha, imprima o número K — o número de componentes fortemente conectados em um determinado gráfico. Na próxima linha, imprima N números — para cada vértice, imprima o número do componente fortemente conectado ao qual esse vértice pertence. Os componentes fortemente conectados devem ser numerados de forma que, para qualquer aresta, o número do componente fortemente conectado de seu início não exceda o número do componente fortemente conectado de seu final.

Entrar Saída
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!