دنده
Problem
در یک گراف بدون جهت n رأس وجود دارد، اما هیچ لبه ای ندارد. m یال ها به تدریج به نمودار اضافه می شوند.
پس از هر افزودن یک لبه، باید تعداد اجزای متصل را پیدا کنید.
یک نمودار می تواند دارای حلقه ها و چندین یال باشد.
ورودی:
سطر اول شامل دو عدد است - n و m (1 <= n <= 300000، 0 <= m <= 500000) - تعداد رئوس نمودار و تعداد یال های اضافه شده.
خطوط m بعدی شامل دو عدد u, v (1 <= u, v <= n) هستند - به این معنی که یک یال (u, v) به نمودار اضافه شده است.
خروجی:
بعد از هر اضافه کردن یک یال، تعداد اجزای متصل شده نمودار را چاپ کنید.
<بدن>
|
وارد کنید |
خروجی |
|
3 2
1 2
2 3
|
2
1 |
|
36
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(ج) ابراهیم احمد، 2018