جستجو برای اجزای قوی متصل
Problem
به شما یک نمودار جهت دار با N رأس و M یال (1<=N<=20000، 1<=M<=200000) داده می شود. مولفه های به شدت متصل گراف داده شده را بیابید و تراکم آن را به صورت توپولوژیکی مرتب کنید.
ورودی
نمودار در فایل ورودی به صورت زیر آورده شده است: خط اول شامل اعداد N و M است. هر یک از خطوط M بعدی حاوی توضیحات لبه — دو عدد صحیح از 1 تا N — اعداد شروع و پایان لبه.
خروجی
در خط اول عدد K — تعداد مؤلفه‌های قویاً متصل در یک نمودار مشخص. در خط بعدی N عدد — برای هر رأس، تعداد مؤلفه‌ای که قویاً به آن متصل است را چاپ کنید. اجزای متصل قوی باید به گونه‌ای شماره‌گذاری شوند که برای هر یال، تعداد مؤلفه‌های متصل قوی ابتدای آن از تعداد مؤلفه‌های متصل قوی انتهای آن تجاوز نکند.
<بدن>
|
وارد کنید |
خروجی |
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
|