Problem
Anda diberi graf terarah dengan N bucu dan tepi M (1<=N<=20000, 1<=M<=200000). Cari komponen bersambung kuat bagi graf yang diberikan dan susun pemeluwapannya secara topologi.
Input
Graf diberikan dalam fail input seperti berikut: baris pertama mengandungi nombor N dan M. Setiap baris M seterusnya mengandungi penerangan tentang tepi — dua integer dari 1 hingga N — nombor permulaan dan tamat tepi.
Output
Pada baris pertama cetak nombor K — bilangan komponen bersambung kuat dalam graf tertentu. Pada baris seterusnya cetak N nombor — untuk setiap bucu mencetak nombor komponen bersambung kuat yang dimiliki bucu ini. Komponen bersambung kuat mesti dinomborkan sedemikian rupa sehingga untuk sebarang tepi bilangan komponen bersambung kuat pada permulaannya tidak melebihi bilangan komponen bersambung kuat pada hujungnya.
|
Masukkan |
Output |
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
|