Recherche de composants fortement connectés
Problem
On vous donne un graphe orienté avec N sommets et M arêtes (1<=N<=20000, 1<=M<=200000). Trouvez les composants fortement connectés du graphe donné et triez topologiquement sa condensation.
Entrée
Le graphe est donné dans le fichier d'entrée comme suit : la première ligne contient les nombres N et M. Chacune des M lignes suivantes contient une description de l'arête — deux entiers de 1 à N — numéros de début et de fin des bords.
Sortie
Sur la première ligne, écrivez le numéro K — le nombre de composantes fortement connectées dans un graphe donné. Sur la ligne suivante, écrivez N nombres — pour chaque sommet imprimer le numéro de la composante fortement connexe à laquelle appartient ce sommet. Les composantes fortement connexes doivent être numérotées de telle sorte que pour toute arête le numéro de la composante fortement connexe de son début ne dépasse pas le numéro de la composante fortement connexe de sa fin.
Entrez
Sortie
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