Problem
Yönsüz bir grafikte n tane köşe vardır, ancak kenarları yoktur. m kenarlar kademeli olarak grafiğe eklenir.
Bir kenarın her eklenmesinden sonra, bağlı bileşenlerin sayısını bulmanız gerekir.
Bir grafiğin döngüleri ve birden çok kenarı olabilir.
Giriş:
İlk satır iki sayı içerir - n ve m (1 <= n <= 300000, 0 <= m <= 500000) - grafik köşelerinin sayısı ve eklenen kenarların sayısı.
Sonraki m satır iki sayı içerir u, v (1 <= u, v <= n) - bunlar grafiğe bir kenar (u, v) eklendiği anlamına gelir.
Çıktı:
Her kenar eklemesinden sonra, grafiğin bağlı bileşenlerinin sayısını yazdırın.
|
Gir |
Çıktı |
|
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
|
(c) İbrahim Ahmed, 2018