Suche nach einer starken Konnektivitätskomponente
Problem
Sie haben einen orientierten Graph mit N Scheitelpunkten und M Kanten (1<=N<=20000, 1<=M<=200000). Suchen Sie die Komponenten der starken Konnektivität des angegebenen Diagramms und sortieren Sie die Kondensation topologisch.
Eingabe
Das Diagramm wird in der Eingabedatei wie folgt angegeben: Die erste Zeile enthält die Zahlen N und M. Jede der folgenden M Zeilen enthält eine Beschreibung der Kante: zwei ganze Zahlen zwischen 1 und N — die Anfangs- und Endnummern der Kante.
Ausgabe
Geben Sie in der ersten Zeile die Anzahl K aus, die die Komponente für starke Konnektivität im angegebenen Diagramm enthält. Geben Sie in der nächsten Zeile N Zahlen aus — Geben Sie für jeden Stützpunkt die Nummer der Komponente der starken Konnektivität aus, zu der dieser Stützpunkt gehört. Die Komponenten mit starker Konnektivität müssen so nummeriert sein, dass die Anzahl der Komponenten mit starker Konnektivität des Anfangs für jede Kante die Anzahl der Komponenten mit starker Konnektivität des Endes nicht überschreitet.
|
Eingabe |
Ausgabe |
|
10 19
1 4
7 8
5 10
8 9
9 6
2 6
6 2
3 8
9 2
7 2
9 7
4 5
3 6
7 3
6 7
10 8
10 1
2 9
2 7
|
2
1 2 2 1 1 2 2 2 2 1
|