يتم إعطاؤك رسمًا بيانيًا موجهًا برؤوس N وحواف M (1 & lt ؛ = N & lt ؛ = 20000 ، 1 & lt ؛ = M & lt ؛ = 200000). أوجد المكونات شديدة الارتباط في الرسم البياني المعطى وفرز تكاثفه طوبولوجيًا.
يتم تقديم الرسم البياني في ملف الإدخال على النحو التالي: يحتوي السطر الأول على الأرقام N و M. يحتوي كل سطر من سطور M التالية على وصف للحافة & [مدش] ؛ رقمين صحيحين من 1 إلى N و [مدش] ؛ حافة البداية ونهاية الأرقام.
نبسب ؛
الإخراج
في السطر الأول ، قم بطباعة الرقم K & [مدش] ؛ عدد المكونات المتصلة بقوة في رسم بياني معين. في السطر التالي ، قم بطباعة N أرقام و [مدش] ؛ لكل رأس طباعة رقم المكون المتصل بقوة التي ينتمي إليها هذا الرأس. يجب ترقيم المكونات المتصلة بقوة بحيث لا يتجاوز رقم المكون المتصل بقوة في بدايته ، لأي حافة ، عدد المكون المتصل بقوة في نهايته.
<الجسم>
|
أدخل |
الإخراج |
10 19
14 / div>
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 & nbsp؛
|