DSU dengan Kompresi Jalur
Menemukan dan menggabungkan dalam waktu hampir konstan
DSU dengan Kompresi Jalur adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang Dilacak DSU
Penggabungan Himpunan Saling Lepas menjaga elemen tetap berada dalam himpunan yang tidak saling tumpang tindih, sehingga Anda dapat memeriksa apakah dua elemen sudah berada dalam satu himpunan. 🤝
Himpunan sebagai Pohon
DSU menyimpan setiap himpunan sebagai pohon. Setiap elemen menunjuk ke induk, dan simpul paling atas, yaitu akar, merupakan nama unik seluruh kelompok.
Larik Induk
Anda menyimpan semua tautan tersebut dalam satu larik. Mulailah dengan setiap elemen sebagai induk bagi dirinya sendiri, yang berarti setiap elemen awalnya berada dalam himpunannya sendiri.
parent = list(range(n))Menemukan Akar
Operasi find menelusuri tautan induk hingga sebuah elemen menunjuk kepada dirinya sendiri. Simpul yang menunjuk kepada dirinya sendiri itulah akar yang mengidentifikasi himpunan tersebut.
while parent[x] != x:
x = parent[x]Rantai Panjang Menimbulkan Masalah
Tanpa penanganan yang tepat, himpunan dapat membentuk rantai panjang dan ramping. Akibatnya, find menelusuri simpul demi simpul dan satu kueri dapat berbiaya O(n), yang terlalu lambat.
Perkenalkan Kompresi Jalur
Kompresi jalur mengatasi hal ini: saat mencari akar, arahkan kembali setiap simpul yang dikunjungi langsung ke akar, sehingga pohon menjadi lebih datar untuk penggunaan berikutnya. ⚡
Kompresi Rekursif
Cara yang paling rapi adalah menggunakan rekursi. Temukan akar, lalu simpan kembali akar tersebut ke dalam parent[x] sebelum mengembalikannya, sehingga tautannya menjadi lebih pendek secara permanen.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Dua Elemen, Himpunan Sama?
Untuk menguji apakah dua elemen terhubung, bandingkan akar keduanya. Jika find(a) sama dengan find(b), keduanya berada dalam kelompok yang sama; jika tidak, keduanya masih terpisah.
if find(a) == find(b):
print("connected")Menggabungkan Dua Himpunan
Operasi union menggabungkan kelompok dengan menunjuk salah satu akar ke akar lainnya. Satu baris menghubungkan dua pohon utuh menjadi satu himpunan.
def union(a, b):
parent[find(a)] = find(b)Mengapa Ini Begitu Cepat
Dengan kompresi saja, operasi berjalan dalam sekitar O(log n) secara teramortisasi, dan jika dipadukan dengan pemeringkatan, waktunya mendekati konstan untuk setiap kueri.
Keunggulan DSU
DSU mendukung pertanyaan tentang keterhubungan: lingkaran pertemanan, komponen jaringan, dan pohon merentang Kruskal semuanya mengandalkan find dan union yang cepat. 🌐
Pemeriksaan Singkat
Pertimbangkan perubahan yang sebenarnya dilakukan oleh kompresi jalur.
Ringkasan
Anda membangun DSU: larik induk, find untuk mendapatkan akar, dan union untuk menggabungkan. Kompresi jalur membuatnya sangat cepat. Kerja bagus! 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “DSU dengan Kompresi Jalur” gratis?
Ya — teks lengkap “DSU dengan Kompresi Jalur” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “DSU dengan Kompresi Jalur”?
Menemukan dan menggabungkan dalam waktu hampir konstan Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “DSU dengan Kompresi Jalur” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- DSU dengan Kompresi Jalur
- Union berdasarkan Rank dan Komponen
- Minimum Spanning Tree Kruskal
- MST Prim dengan Heap