Körpülər: son döyüş#4326
Tezisin praktiki tətbiqləri varmı?
_____________________________________________________
Populyar sual
Əfsanə
Sergey tezisini tamamlamağa yaxındır. Dekabrdan bəri mövzu dəyişməyib: "Dinamik 2-ətrəfli-bağlantılılıq Problemi." Bir alqoritm hazırlanıb, test edilib və onun O(K \log K) mürəkkəbliyi sübut olunub. İndi isə yalnız "praktiki tətbiqlər" fəsli yazılmalıdır.
Amma "Dinamik 2-ətrəfli-bağlantılılıq Problemi"nin hansı praktik istifadəsi ola bilər? Bu, bəlkə də problemin özündən belə çətin sualdır. Ancaq tezisi müdafiə etmək lazımdır, ona görə də təcili cavab tapılmalıdır.
Ona görə də burada bir praktiki tətbiq var: bu mövzuda bir müsabiqə məsələsi hazırlamaq olar!
Məsələ
Sizə ən çoxu 10^5 təpədən ibarət bir istiqamətsiz qraf verilir. Əvvəlcə qrafda heç bir kənar yoxdur. Siz ADD və DEL tipli sorğuları işləyəcəksiniz—yəni və təpələri arasına kənar əlavə etmək və ya silmək.
İstənilən anda siz cari qrafda neçə körpü olduğunu müəyyən etməlisiniz.
Heç vaxt qrafda heç bir anda çoxlu kənar və ya döngə olmayacaq.
Əgər "kənarı sil" əmri verilərsə, həmin anda o kənarın qrafda olduğu zəmanət verilir.
İpuçları
Tezis məhz ona görə "tezis" adlanır ki, onu sadəcə 5 saata yazmaq mümkün deyil. Odur ki, burada 5 ipucu var:
Kənar əlavə edin və silin—kənarı müəyyən zaman intervalında "canlı" edin.
"Böl və idarə et" yanaşmasından istifadə edin.
İkitərəfli bağlı komponentləri sıxlaşdırın.
İkitərəfli bağlı komponentləri sıxlaşdırdıqdan sonra belə, əgər sorğuların sayı azdırsa, qrafı daha da sıxalda bilərsiniz.
O(K \log K) həlli mövcuddur.
Birinci sətirdə iki tam ədəd və verilir: uyğun olaraq, təpələrin və sorğuların sayı (1 \le N \le 10^5, 1 \le K \le 10^5).
Növbəti sətrin hər birində bir sorğu verilib. Bütün sorğular ya ADD, ya da DEL sözü ilə başlayır (uyğun olaraq, kənar əlavə etmək və ya silmək üçün). Bu sözdən sonra və olmaqla iki tam ədəd gəlir və bunlar kənarın uclarını göstərir (1 \le a, b \le N, a \ne b).
Hər bir sorğudan sonra bir tam ədəd çıxışa verin: qrafda hal-hazırda olan körpülərin sayı.
Nümunə 1