Petunjuk dan konteks
Anda menerima n pengguna dan q operasi berstempel waktu. add id u v menambahkan hubungan tak berarah dengan sebuah ID, remove id menghapusnya, dan ask u v menanyakan apakah dua pengguna terhubung pada waktu tersebut. Setiap hubungan ditambahkan dan dihapus paling banyak satu kali, dan semua operasi telah diketahui sebelum jawaban dibuat.
Kembalikan jawaban Boolean untuk setiap ask. Jelaskan mengapa disjoint-set union biasa tidak dapat memproses penghapusan dengan aman, cara memetakan masa aktif hubungan ke dalam garis waktu, cara memulihkan status, serta batas dan kompleksitas mana yang penting. Targetnya adalah konektivitas dinamis offline, bukan pembaruan online yang arbitrer.
Apa yang sedang diuji oleh pewawancara
- Apakah Anda menyadari bahwa invarian union-find yang monotonik rusak ketika edge menghilang.
- Apakah Anda dapat merepresentasikan setiap edge sebagai interval masa aktif setengah terbuka
[add time, remove time). - Apakah Anda dapat menguraikan sebuah interval ke dalam node segment tree
O(log q). - Apakah Anda dapat mengimplementasikan rollback DSU tanpa path compression dan dengan union by size.
- Apakah Anda dapat menghubungkan snapshot, pengembalian rekursi, dan kebenaran kueri.
Pertanyaan untuk diklarifikasi terlebih dahulu
- Apakah semua operasi diketahui sebelumnya? Jika jawaban harus online, pendekatan garis waktu tidak berlaku.
- Apakah setiap hubungan memiliki ID unik? Tanpa ID unik, penghapusan edge duplikat menjadi ambigu.
- Apakah grafnya tak berarah? Graf berarah memerlukan struktur keterjangkauan yang berbeda.
- Bisakah sebuah ID ditambahkan lagi setelah dihapus? Jika ya, setiap masa aktif memerlukan intervalnya sendiri.
- Apakah kueri hanya berupa konektivitas, atau juga ukuran komponen, jalur terpendek, atau jalur sebenarnya?
Kerangka jawaban 30 detik
DSU biasa dapat menggabungkan komponen tetapi tidak dapat menghapus edge tanpa mengetahui struktur mana yang harus dipecah. Saya akan memindai operasi, membuat [add, remove) untuk setiap edge, dan memperpanjang edge tanpa penghapusan hingga q. Saya akan menempatkan setiap interval dalam segment tree berdasarkan waktu. Selama DFS, terapkan edge dari suatu node, jawab kueri pada daun (leaf), dan lakukan rollback ke snapshot saat masuk ketika meninggalkan node. Rollback DSU menghindari path compression dan menggunakan union by size, sehingga setiap perubahan dicatat dan total biayanya adalah O(q log q log n) dengan ruang O(n + q log q).
Pembahasan mendalam langkah demi langkah
Langkah 1: Identifikasi mengapa DSU biasa gagal
DSU biasa menyimpan hasil dari semua penggabungan yang terlihat sejauh ini. Menghapus satu edge mungkin membiarkan komponen tetap terhubung melalui edge lain atau mungkin mengharuskan pemisahan pohon; pointer parent saja tidak menunjukkan cut yang terpengaruh. Tidak ada "kebalikan union" yang aman.
Langkah 2: Bangun interval masa aktif edge
Catat setiap waktu add. Ketika remove muncul, tutup [add, remove); bentuk setengah terbuka menjaga edge tidak aktif pada stempel waktu penghapusan. Edge yang masih terbuka di akhir menjadi [add, q).
Langkah 3: Tutupi interval dengan segment tree
Simpan interval dalam node segment-tree yang menutupinya secara penuh. Satu interval menempati paling banyak O(log q) node. Setiap edge yang disimpan di suatu node valid untuk seluruh rentang waktu node tersebut, sehingga digabungkan sekali daripada di setiap daun.
Langkah 4: Rancang rollback DSU
Pertahankan parent dan size. find mengikuti parent tanpa path compression. union menempelkan akar yang lebih kecil ke akar yang lebih besar dan memasukkan child yang diubah, akar, serta ukuran lama ke dalam history stack. Union by size membatasi tinggi pohon sebesar O(log n).
Langkah 5: DFS dengan snapshot dan pemulihan
Simpan panjang riwayat saat masuk, terapkan edge node, dan jawab ask di daun. Setelah kedua anak selesai, lakukan pop kembali ke panjang yang disimpan. Edge parent tetap aktif untuk anak berikutnya, sementara edge khusus anak tidak dapat bocor ke sesama saudara (sibling).
Langkah 6: Bentuk implementasi
Implementasi memiliki empat fase: membangun interval setengah terbuka, menambahkan setiap interval ke time segment tree, melakukan traversal dengan rollback DSU, dan menjawab pada daun. Detail kritisnya adalah tidak ada path compression, mencatat ukuran komponen lama, dan memulihkan tepat ke snapshot.
Langkah 7: Buktikan invarian dan kompleksitas
Saat masuk ke node segment-tree, DSU berisi tepat edge yang aktif di seluruh rentang node tersebut ditambah edge yang diterapkan oleh leluhur. Edge anak hanya ada di dalam subtree anak dan dihapus saat kembali, sehingga daun melihat tepat gabungan edge aktif. Setiap edge disimpan di O(log q) node dan setiap penggabungan membutuhkan biaya O(log n) dengan union by size, menghasilkan waktu O(q log q log n) dan penyimpanan O(n + q log q).
Langkah 8: Bandingkan alternatif dan kasus kegagalan
Jika edge hanya bertambah dan konektivitas dikueri, DSU biasa lebih sederhana dengan operasi teramortisasi yang hampir konstan. Penghapusan online yang sebenarnya memerlukan struktur dynamic-connectivity; pohon garis waktu tidak dapat mengetahui penghapusan di masa mendatang yang belum diketahui. DSU juga tidak dapat menjawab jalur terpendek, yang memerlukan BFS, Dijkstra, atau struktur jalur lainnya.
Contoh jawaban berkualitas tinggi
Saya pertama-tama akan mengonfirmasi bahwa setiap operasi diketahui dan setiap hubungan memiliki ID yang stabil. DSU biasa hanya menggabungkan, dan penghapusan merusak invarian komponennya, jadi saya akan memindai operasi ke dalam masa aktif edge setengah terbuka dan memperpanjang edge yang masih terbuka hingga akhir. Saya akan menempatkan interval tersebut dalam segment tree berdasarkan waktu, menggabungkan edge node selama DFS, menjawab konektivitas di daun, dan melakukan rollback ke panjang riwayat saat masuk saat kembali. Rollback DSU menghindari path compression, menggunakan union by size, dan mencatat perubahan parent serta ukuran, menghasilkan tinggi pohon O(log n). Setiap edge muncul di O(log q) node, jadi waktunya adalah O(q log q log n) dan ruangnya adalah O(n + q log q). Untuk penambahan saja saya akan menggunakan DSU biasa; untuk penghapusan online atau jalur terpendek saya akan memilih struktur dinamis yang lebih kuat.
Kesalahan umum
- Membalikkan penggabungan untuk penghapusan → penggabungan tidak dapat dibalikkan → gunakan interval masa aktif dan rollback.
- Menggunakan path compression dalam rollback DSU → banyak penulisan parent tidak tercatat → gunakan union by size tanpa kompresi.
- Memperlakukan masa aktif sebagai tertutup
[add, remove]→ edge tetap aktif saat penghapusan → gunakan[add, remove). - Menggabungkan ulang setiap edge di setiap daun → kompleksitas kehilangan manfaat segment-tree → gabungkan pada node yang menutupi.
- Hanya memulihkan pointer parent → pilihan union-by-size berikutnya menjadi rusak → pulihkan ukuran lama juga.
- Menjanjikan metode offline untuk pembaruan online → interval masa depan tidak diketahui → konfirmasikan model interaksi terlebih dahulu.
Pertanyaan lanjutan dan jawaban
Bagaimana jika ID hubungan yang sama ditambahkan lagi setelah dihapus?
Buat catatan terbuka baru untuk setiap add, dan biarkan remove hanya menutup masa aktif yang sedang terbuka saat itu. ID yang sama kemudian menghasilkan beberapa interval yang saling lepas alih-alih menimpa yang lama.
Bisakah rancangan yang sama menjawab ukuran komponen saat ini?
Ya. Pertahankan size akar, kembalikan akar dari find, dan pulihkan ukuran lama selama rollback. Agregat komponen tambahan juga memerlukan nilai lama pada history stack dan pembaruan yang dapat dibalik.
Bagaimana jika q sangat besar sehingga rekursi atau memori menjadi bottleneck?
Periksa terlebih dahulu apakah penyimpanan interval O(q log q) mencukupi. Kemudian ganti DFS rekursif dengan stack eksplisit, padatkan penyimpanan edge, atau proses blok waktu. Jangan aktifkan path compression karena dapat secara diam-diam merusak kebenaran rollback.
Mengapa metode garis waktu tidak dapat diubah begitu saja menjadi penghapusan online?
Metode ini membutuhkan stempel waktu penghapusan untuk membangun setiap interval. Masukan online tidak mengungkapkan stempel waktu masa depan tersebut, sehingga pra-pemrosesan tidak dapat menempatkan edge di dalam pohon. Gunakan struktur yang dirancang untuk dynamic connectivity online dan evaluasi kembali latensi serta biaya implementasinya.