0Pricing
Coding Interview Prep · Pelajaran

Union berdasarkan Rank dan Komponen

Menjaga tree tetap datar dan menghitung kelompok

Union berdasarkan Rank dan Komponen adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

union Dapat Dilakukan Secara Asal-asalan

union biasa hanya menempatkan satu akar di bawah akar lainnya. Jika dilakukan tanpa hati-hati, cara ini dapat membangun pohon tinggi yang lambat, sehingga kita memerlukan cara yang lebih cerdas untuk menggabungkan akar.

Gagasan Utama

union berdasarkan peringkat selalu menempatkan pohon yang lebih pendek di bawah pohon yang lebih tinggi. Menjaga pohon tetap dangkal membuat setiap find berikutnya lebih cepat. 📏

Arti Peringkat

Peringkat adalah perkiraan ketinggian sebuah pohon. Setiap elemen mulai dengan peringkat 0 karena satu simpul tidak memiliki kedalaman di bawahnya.

rank = [0] * n

Pasang yang Lebih Pendek ke yang Lebih Tinggi

Bandingkan peringkat kedua akar. Akar dengan peringkat lebih kecil menjadi anak, sehingga pohon gabungan tetap sedatar mungkin.

if rank[ra] < rank[rb]:
    parent[ra] = rb

Jika Seri, Naikkan Peringkat

Jika kedua akar memiliki peringkat yang sama, pilih salah satunya sebagai akar baru dan naikkan peringkatnya satu tingkat karena pohon baru saja bertambah tinggi satu tingkat.

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Variasi union Berdasarkan Ukuran

Alternatif yang populer adalah union berdasarkan ukuran: tempatkan himpunan yang lebih kecil di bawah himpunan yang lebih besar. Cara ini sama efektifnya dan memberi Anda ukuran kelompok tanpa biaya tambahan.

Menghitung Komponen

Mulai jumlah pada n karena setiap elemen merupakan kelompoknya sendiri. Setiap union yang berhasil menggabungkan dua kelompok menjadi satu, sehingga jumlahnya dikurangi satu.

components = n

Lewati union Tanpa Operasi

Jika dua elemen sudah memiliki akar yang sama, union tidak melakukan apa pun. Kurangi jumlah hanya ketika akar keduanya benar-benar berbeda.

if find(a) != find(b):
    union(a, b)
    components -= 1

Peringkat Ditambah Kompresi

Gabungkan union berdasarkan peringkat dengan kompresi jalur, maka DSU berjalan dalam waktu invers-Ackermann, yang secara efektif konstan untuk masukan nyata apa pun. ⚡

Ukuran Himpunan Saat Diperlukan

Dengan union berdasarkan ukuran, Anda dapat langsung mengetahui seberapa besar suatu kelompok: cukup baca ukuran yang tersimpan pada akar elemen tersebut.

group = size[find(x)]

Di Mana Ini Berguna

Penghitungan komponen menjawab pertanyaan klasik seperti jumlah lingkaran pertemanan atau wilayah yang terhubung setelah rangkaian pemanggilan penggabungan. 🌐

Pemeriksaan Singkat

Bernalarlah tentang perubahan yang terjadi pada penghitung komponen.

Rangkuman

Anda mempelajari penggabungan berdasarkan peringkat untuk menjaga pohon tetap datar, serta cara melacak jumlah komponen dan ukuran kelompok. DSU kini sangat cepat! 🎉

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Union berdasarkan Rank dan Komponen” gratis?

Ya — teks lengkap “Union berdasarkan Rank dan Komponen” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Union berdasarkan Rank dan Komponen”?

Menjaga tree tetap datar dan menghitung kelompok Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 2 dari 4.

Berapa lama pelajaran “Union berdasarkan Rank dan Komponen” 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 Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep 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

  1. DSU dengan Kompresi Jalur
  2. Union berdasarkan Rank dan Komponen
  3. Minimum Spanning Tree Kruskal
  4. MST Prim dengan Heap
← Kembali ke Coding Interview Prep