Cerca componenti fortemente connessi
Problem
Viene fornito un grafo orientato con N vertici e M archi (1<=N<=20000, 1<=M<=200000). Trova le componenti fortemente connesse del grafo dato e ordina topologicamente la sua condensazione.
Input
Il grafico viene fornito nel file di input come segue: la prima riga contiene i numeri N e M. Ognuna delle M righe successive contiene una descrizione del bordo — due numeri interi da 1 a N — numeri di inizio e fine del bordo.
Uscita
Sulla prima riga stampa il numero K — il numero di componenti fortemente connesse in un dato grafo. Sulla riga successiva stampa N numeri — per ogni vertice stampa il numero della componente fortemente connessa a cui appartiene questo vertice. Le componenti fortemente connesse devono essere numerate in modo tale che per ogni spigolo il numero della componente fortemente connessa del suo inizio non superi il numero della componente fortemente connessa della sua estremità.
|
Entra |
Uscita |
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
|
2
1 2 2 1 1 2 2 2 2 1
|