Prompt dan konteks
Anda menerima n pengguna dan q operasi bercap masa. add id u v menambah hubungan tidak berarah dengan ID, remove id memadamkannya, dan ask u v bertanyakan sama ada dua pengguna bersambung pada masa itu. Setiap hubungan ditambah dan dipadamkan paling banyak sekali, dan semua operasi diketahui sebelum jawapan dihasilkan.
Kembalikan jawapan Boolean bagi setiap ask. Terangkan sebab disjoint-set union biasa tidak dapat memproses pemadaman dengan selamat, cara memetakan jangka hayat hubungan ke garis masa, cara memulihkan keadaan, dan sempadan serta kekompleksan yang penting. Sasaran ialah ketersambungan dinamik luar talian, bukan kemas kini dalam talian sewenang-wenangnya.
Perkara yang diuji oleh penemu duga
- Sama ada anda menyedari bahawa invarian union-find monotonik rosak apabila tepi hilang.
- Sama ada anda boleh mewakili setiap tepi sebagai selang jangka hayat separuh terbuka
[add time, remove time). - Sama ada anda boleh menguraikan selang kepada nod pepohon segmen
O(log q). - Sama ada anda boleh melaksanakan DSU rollback tanpa pemampatan laluan dan dengan cantuman mengikut saiz (union by size).
- Sama ada anda boleh menghubungkan syot kilat (snapshots), pemulangan rekursi dan ketepatan pertanyaan.
Soalan untuk dijelaskan terlebih dahulu
- Adakah semua operasi diketahui lebih awal? Jika jawapan mesti dalam talian, pendekatan garis masa tidak terpakai.
- Adakah setiap hubungan mempunyai ID yang unik? Tanpa ID, pemadaman tepi pendua adalah kabur.
- Adakah graf tidak berarah? Graf berarah memerlukan struktur ketercapaian yang berbeza.
- Bolehkah ID ditambah semula selepas pemadaman? Jika ya, setiap jangka hayat memerlukan selangnya sendiri.
- Adakah pertanyaan hanya ketersambungan, atau juga saiz komponen, laluan terpendek, atau laluan sebenar?
Rangka kerja jawapan 30 saat
DSU biasa boleh mencantumkan komponen tetapi tidak boleh memadamkan tepi tanpa mengetahui struktur mana yang mesti dipecahkan. Saya akan mengimbas operasi, mencipta [add, remove) untuk setiap tepi, dan memanjangkan tepi tanpa pemadaman kepada q. Saya akan meletakkan setiap selang dalam pepohon segmen merentasi masa. Semasa DFS, gunakan tepi nod, jawab pertanyaan pada daun, dan rollback ke syot kilat semasa masuk apabila meninggalkan nod. DSU rollback mengelakkan pemampatan laluan dan menggunakan union by size, jadi setiap perubahan direkodkan dan kos keseluruhan ialah O(q log q log n) dengan ruang O(n + q log q).
Perbincangan mendalam langkah demi langkah
Langkah 1: Kenal pasti sebab DSU biasa gagal
DSU biasa menyimpan hasil daripada semua cantuman yang dilihat setakat ini. Mengalih keluar satu tepi mungkin meninggalkan komponen yang masih disambungkan melalui tepi lain atau mungkin memerlukan pemisahan pepohon; penuding induk sahaja tidak mendedahkan potongan (cut) yang terjejas. Tiada "cantuman songsang" yang selamat.
Langkah 2: Bina selang jangka hayat tepi
Catat setiap masa add. Apabila remove muncul, tutup [add, remove); bentuk separuh terbuka memastikan tepi tiada pada cap masa pemadaman. Tepi yang masih terbuka pada akhirnya menjadi [add, q).
Langkah 3: Tutup selang dengan pepohon segmen
Simpan selang dalam nod pepohon segmen yang menutupinya sepenuhnya. Satu selang menduduki paling banyak O(log q) nod. Setiap tepi yang disimpan pada nod adalah sah untuk keseluruhan julat masa nod tersebut, jadi ia dicantumkan sekali dan bukannya pada setiap daun.
Langkah 4: Reka bentuk DSU rollback
Kekalkan parent dan size. find mengikut induk tanpa pemampatan laluan. union menyambungkan punca yang lebih kecil kepada punca yang lebih besar dan menolak anak yang diubah, punca dan saiz lama ke atas tindanan sejarah (history stack). Union by size mengehadkan ketinggian pepohon kepada O(log n).
Langkah 5: DFS dengan syot kilat dan pemulihan
Simpan panjang sejarah semasa masuk, gunakan tepi nod, dan jawab ask pada daun. Selepas kedua-dua anak selesai, pop kembali ke panjang yang disimpan. Tepi induk kekal aktif untuk anak seterusnya, manakala tepi khusus anak tidak boleh bocor merentasi nod adik-beradik.
Langkah 6: Bentuk pelaksanaan
Pelaksanaan mempunyai empat fasa: membina selang separuh terbuka, menambah setiap selang pada pepohon segmen masa, melintasi dengan DSU rollback, dan menjawab daun. Butiran kritikal adalah tiada pemampatan laluan, merekodkan saiz komponen lama, dan memulihkan tepat kepada syot kilat.
Langkah 7: Buktikan invarian dan kekompleksan
Semasa masuk ke nod pepohon segmen, DSU mengandungi tepat tepi yang aktif sepanjang julat nod itu ditambah tepi yang digunakan oleh leluhur. Tepi anak hanya wujud dalam sub-pepohon anak dan dialih keluar apabila kembali, jadi daun melihat tepat cantuman tepi aktif. Setiap tepi disimpan dalam O(log q) nod dan setiap cantuman menelan kos O(log n) dengan union by size, memberikan masa O(q log q log n) dan storan O(n + q log q).
Langkah 8: Bandingkan alternatif dan kes kegagalan
Jika tepi hanya ditambah dan ketersambungan ditanya, DSU biasa adalah lebih mudah dengan operasi terpelunasan (amortized) yang hampir malar. Pemadaman dalam talian yang sebenar memerlukan struktur dynamic-connectivity; pepohon garis masa tidak dapat mengetahui pemadaman masa hadapan yang belum diketahui. DSU juga tidak boleh menjawab laluan terpendek, yang memerlukan BFS, Dijkstra, atau struktur laluan lain.
Contoh jawapan berkualiti tinggi
Mula-mula saya akan mengesahkan bahawa setiap operasi diketahui dan setiap hubungan mempunyai ID yang stabil. DSU biasa hanya mencantumkan, dan pemadaman memecahkan invarian komponennya, jadi saya akan mengimbas operasi ke dalam jangka hayat tepi separuh terbuka dan memanjangkan tepi yang masih terbuka hingga akhir. Saya akan meletakkan selang tersebut dalam pepohon segmen merentasi masa, mencantumkan tepi nod semasa DFS, menjawab ketersambungan pada daun, dan rollback kepada panjang sejarah kemasukan apabila kembali. DSU rollback mengelakkan pemampatan laluan, menggunakan union by size, dan merekodkan perubahan induk serta saiz, memberikan ketinggian pepohon O(log n). Setiap tepi muncul dalam O(log q) nod, jadi masa ialah O(q log q log n) dan ruang ialah O(n + q log q). Untuk penambahan sahaja saya akan menggunakan DSU biasa; untuk pemadaman dalam talian atau laluan terpendek saya akan memilih struktur dinamik yang lebih kukuh.
Kesilapan biasa
- Mengundurkan cantuman untuk pemadaman → cantuman tidak boleh disongsangkan → gunakan selang jangka hayat dan rollback.
- Menggunakan pemampatan laluan dalam DSU rollback → banyak penulisan induk tidak dilog → gunakan union by size tanpa pemampatan.
- Memperlakukan jangka hayat sebagai tertutup
[add, remove]→ tepi kekal aktif semasa pemadaman → gunakan[add, remove). - Mencantumkan semula setiap tepi pada setiap daun → kekompleksan kehilangan manfaat pepohon segmen → cantumkan pada nod yang menutupi.
- Memulihkan penuding induk sahaja → pilihan union-by-size yang seterusnya menjadi rosak → pulihkan saiz lama juga.
- Menjanjikan kaedah luar talian untuk kemas kini dalam talian → selang masa hadapan tidak diketahui → sahkan model interaksi terlebih dahulu.
Soalan susulan dan respons
Bagaimana jika ID hubungan yang sama ditambah semula selepas pemadaman?
Cipta rekod terbuka baharu untuk setiap add, dan biarkan remove menutup hanya jangka hayat yang sedang terbuka. ID yang sama kemudiannya menghasilkan berbilang selang yang tidak bersilang dan bukannya menulis ganti selang yang lama.
Bolehkah reka bentuk yang sama menjawab saiz komponen semasa?
Ya. Kekalkan punca size, kembalikan punca daripada find, dan pulihkan saiz lama semasa rollback. Agregat komponen tambahan juga memerlukan nilai lama pada tindanan sejarah dan kemas kini yang boleh diterbalikkan.
Bagaimana jika q terlalu besar sehingga rekursi atau memori menjadi kekangan (bottleneck)?
Semak sama ada storan selang O(q log q) mencukupi terlebih dahulu. Kemudian gantikan DFS rekursif dengan tindanan eksplisit, padatkan storan tepi, atau proses blok masa. Jangan dayakan pemampatan laluan kerana ia akan merosakkan ketepatan rollback secara senyap.
Mengapakah kaedah garis masa tidak boleh ditukar kepada pemadaman dalam talian begitu sahaja?
Kaedah ini memerlukan cap masa pemadaman untuk membina setiap selang. Input dalam talian tidak mendedahkan cap masa masa hadapan tersebut, jadi prapemprosesan tidak boleh meletakkan tepi dalam pepohon. Gunakan struktur yang direka untuk ketersambungan dinamik dalam talian dan nilai semula kependaman serta kos pelaksanaannya.