Birləşdirmə və ayırma
Siz nə zaman isə dərininə dolaşmaq haqqında eşitmişsinizmi? Məsələn, bu alqoritmdən istifadə etməklə siz qrafın O(E) müddətində asılı olduğunu müəyyənləşdirə bilərsiniz. Siz hətta bu müddətdə asılılıq komponentlərinin sayını da təyin edə bilərsiniz.
Bəs siz nə zaman isə kəsişməyən çoxluqlar sistemi haqqında eşitmişsinizmi? Bu strukturdan istifadə etməklə, siz tez bir zamanda “Qrafa til əlavə etmək" və "Qrafda asılılıq komponentlərinin sayını hesablamaq" kimi sorğuları emal edə bilərsiniz.
Bəs siz nə zaman isə dinamik əlaqəlilik məsələsi haqqında eşitmişsinizmi? Bu məsələdə üç tip sorğu emal etmək lazımdır:
Qrafa til əlavə etmək.
Qrafdan til çıxartmaq.
Qrafda əlaqəlilik komponentlərinin sayını hesablamaq.
Giriş verilənləri
Başlanğıcda qraf boşdur.
İlk sətirdə təpələrin və sorğuların sayını ifadə edən iki N və K (1 ≤ N ≤ 300000, 0 ≤ K ≤ 300000) tam ədədləri verilir. Növbəti K sətrin hər birində sorğular verilir. Üç tip sorğu var:
+ u v: u və v təpələri arasına til əlavə etmək. Belə tilin olmadığına zəmanət verilir.
- u v: u və v arasındakı tili çıxartmaq. Belə tilin olduğuna zəmanət verilir.
?: Qrafda əlaqəlilik komponentlərinin sayını hesablamalı.
Təpələr 1–dən N-ə qədər tam ədədlərlə nömrələnib. Bütün sorğularda u ≠ v. Qraf istiqamətlənməmiş hesab edilir.
Çıxış verilənləri
Bütün "?" tipli sorğular üçün sorğu anındakı əlaqəlilik komponentlərinin sayını hesablayın.