0Pricing
Coding Interview Prep · Pelajaran

DSU dengan Kompresi Jalur

Implementasikan find dengan kompresi jalur agar semua simpul di sepanjang jalur menunjuk langsung ke akar, sehingga find mencapai waktu amortisasi mendekati O(1)

DSU dengan Kompresi Jalur adalah pelajaran Coding Interview Prep 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa Itu DSU?

Penggabungan Himpunan Saling Lepas (DSU), yang juga disebut struktur penggabungan dan pencarian, adalah struktur data yang mempertahankan kumpulan himpunan yang saling lepas (tidak tumpang tindih). Struktur ini mendukung dua operasi inti: find (elemen x termasuk dalam himpunan mana?) dan union (gabungkan himpunan yang memuat x dan y). DSU ideal untuk masalah konektivitas dinamis, ketika kelompok-kelompok bergabung seiring waktu tetapi tidak pernah terpisah.

Setiap elemen awalnya menjadi himpunannya sendiri. Saat memproses sisi atau hubungan, kita menggabungkan himpunan-himpunan tersebut. Tantangannya adalah melakukannya secara efisien — penerapan naif memerlukan O(n) untuk setiap operasi, tetapi dengan optimasi kita dapat mendekati O(1) secara diamortisasi.

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

Masalah pada find Naif

Dalam DSU naif, find(x) menelusuri rantai induk ke atas sampai mencapai simpul yang menunjuk ke dirinya sendiri (akar). Jika pohonnya seimbang, proses ini memerlukan O(log n). Namun, jika kita selalu melakukan union dengan menautkan akar kedua di bawah akar pertama, kita dapat membuat rantai (pohon degenerat) sepanjang n, sehingga setiap operasi find memerlukan O(n).

Pertimbangkan union 0→1→2→3→4 secara berurutan. Panggilan find pada simpul 0 harus menelusuri seluruh rantai. Dengan kompresi jalur, kita mengatasi masalah ini dengan membuat setiap simpul yang dikunjungi menunjuk langsung ke akar selama operasi find itu sendiri.

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

Kompresi Jalur: Rekursif Satu Lintasan

Kompresi jalur memodifikasi operasi find sehingga setelah menemukan akar, setiap simpul di sepanjang jalur diperbarui agar menunjuk langsung ke akar. Panggilan find berikutnya pada simpul-simpul tersebut menjadi O(1). Versi rekursif mencapai hal ini dengan elegan dalam satu lintasan.

Gagasan utamanya: setelah panggilan rekursif mengembalikan akar, kita menetapkan self.parent[x] = root sebelum mengembalikan hasilnya. Hal ini meratakan pohon — semua simpul pada jalur pencarian kini menunjuk langsung ke akar. Ini tidak mengubah himpunan tempat suatu simpul berada; hanya memperpendek jalur pencarian pada pemanggilan berikutnya.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

Kompresi Jalur: Iteratif Dua Lintasan

Versi iteratif dari kompresi jalur menggunakan dua lintasan: lintasan pertama berjalan ke atas untuk menemukan akar; lintasan kedua mengunjungi kembali setiap simpul dalam jalur dan memperbarui induknya agar langsung menunjuk ke akar. Ini menghindari beban tumpukan rekursi dan aman untuk pohon yang sangat dalam, yang mendekati batas rekursi Python.

Pada pendekatan rekursif maupun iteratif, kebenarannya tidak berubah — find tetap mengembalikan akar yang sama. Satu-satunya perbedaan adalah penunjuk induk diperbarui sebagai efek samping, sehingga semua find berikutnya pada simpul-simpul tersebut menjadi O(1).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

Kompleksitas Diamortisasi Kompresi Jalur

Kompresi jalur saja mencapai waktu diamortisasi O(log n) per operasi dalam rangkaian m operasi. Setiap operasi find mungkin mahal saat pertama kali sebuah rantai ditelusuri, tetapi operasi itu meratakan rantai tersebut sehingga setiap find berikutnya pada simpul-simpul itu menjadi O(1). Total pekerjaan tersebar di antara banyak operasi.

Analisis formalnya menggunakan metode fungsi potensial: potensial DSU berkurang setiap kali jalur induk suatu simpul memendek, dan pengurangan ini membayar biaya penelusuran. Tanpa union berdasarkan peringkat, kompresi jalur saja memberikan O(log n) secara diamortisasi — sudah merupakan peningkatan besar dibandingkan O(n) naif.

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

Jumlah Komponen Terhubung

Salah satu penerapan DSU yang umum adalah menghitung komponen terhubung dalam graf. Kita menginisialisasi penghitung components agar sama dengan n (satu untuk setiap simpul). Setiap union yang berhasil (menggabungkan dua himpunan berbeda) mengurangi penghitung sebanyak 1. Pada akhirnya, penghitung tersebut berisi jumlah komponen yang berbeda.

Ini lebih efisien daripada menjalankan BFS atau DFS untuk kueri keterhubungan, terutama ketika sisi datang secara bertahap (secara daring). DSU memproses setiap sisi dalam waktu diamortisasi yang mendekati O(1), terlepas dari kapan sisi tersebut datang.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

DSU untuk Masalah Graf: Jumlah Provinsi

Masalah Jumlah Provinsi memberikan matriks ketetanggaan berukuran n×n dan menanyakan berapa banyak kelompok kota yang terhubung secara langsung atau tidak langsung. Ini tepat merupakan masalah komponen terhubung yang dapat diselesaikan DSU dengan rapi. Kita mengiterasi semua pasangan (i, j) yang memenuhi isConnected[i][j] == 1 dan memanggil union(i, j).

Setelah memproses semua koneksi, dsu.components adalah jawabannya. Cara ini lebih sederhana dan cepat daripada menjalankan BFS dari setiap simpul yang belum dikunjungi, serta dapat menangani representasi matriks secara langsung tanpa perlu membuat daftar ketetanggaan terlebih dahulu.

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

Varian Kompresi Jalur: Pembagian Jalur Menjadi Dua

Selain kompresi dua lintasan, terdapat varian satu lintasan yang lebih sederhana bernama pembagian jalur menjadi dua: saat menelusuri rantai ke atas, kita membuat setiap simpul menunjuk ke simpul kakeknya, bukan ke induknya. Hal ini membagi dua panjang jalur pada setiap penelusuran tanpa lintasan kedua dan mencapai kompleksitas diamortisasi O(alpha(n)) yang sama jika digabungkan dengan union berdasarkan peringkat.

Pembagian jalur menjadi dua sering dipilih dalam pemrograman kompetitif karena berupa satu perulangan yang bersih tanpa rekursi atau penelusuran kedua. Setiap langkah melakukan self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].

class DSUHalving:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point to grandparent
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

Memeriksa Keterhubungan Setelah Union

Untuk memeriksa apakah dua simpul connected (berada dalam komponen yang sama), panggil find(x) == find(y). Jika keduanya mengembalikan akar yang sama, berarti keduanya berada dalam komponen yang sama. Ini adalah kueri connected, dan dengan kompresi jalur kueri ini berjalan dalam waktu diamortisasi yang mendekati O(1).

Dalam soal wawancara, kueri keterhubungan sering muncul berselang-seling dengan operasi union. DSU menangani keduanya secara daring — Anda dapat menyelang-selingkan union dan kueri dalam urutan apa pun. Hal ini membedakan DSU dari algoritma graf statis seperti BFS/DFS, yang harus dijalankan ulang setiap kali terjadi perubahan struktural.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

Jebakan Umum dalam Implementasi DSU

Kesalahan yang sering terjadi adalah memanggil find lalu memodifikasi parent secara keliru. Selalu panggil find pada kedua elemen sebelum memeriksa kesamaan — jika tidak, Anda mungkin membandingkan sebuah simpul dengan akarnya sendiri secara keliru. Jebakan lainnya adalah lupa bahwa union harus tidak melakukan apa pun ketika kedua elemen sudah memiliki akar yang sama.

Di Python, batas kedalaman rekursi (1000 secara bawaan) dapat menyebabkan RecursionError untuk rantai besar dengan find rekursif. Gunakan versi iteratif dua lintasan, naikkan batas dengan sys.setrecursionlimit, atau gunakan pembagian jalur menjadi dua secara iteratif untuk sepenuhnya menghindari rekursi yang dalam.

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

Pelacakan Ukuran DSU

Dalam beberapa masalah, Anda memerlukan ukuran setiap komponen, bukan hanya akarnya. Tambahkan array size yang diinisialisasi dengan semua nilai 1. Saat menggabungkan dua komponen, tambahkan ukuran akar yang lebih kecil ke akar yang lebih besar. Ini memungkinkan kueri ukuran komponen dalam O(1) setelah union apa pun.

Pelacakan ukuran juga menjadi dasar bagi union berdasarkan ukuran (alternatif terhadap union berdasarkan peringkat): selalu tautkan pohon yang lebih kecil ke bawah akar pohon yang lebih besar. Hal ini menjamin tinggi pohon tetap O(log n), sehingga memberikan jaminan asimtotik yang sama seperti union berdasarkan peringkat.

class DSUWithSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

Pemeriksaan Cepat

Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini Anda mempelajari: DSU mempertahankan himpunan saling lepas dengan operasi find dan union, kompresi jalur meratakan pohon dengan membuat semua simpul yang dilalui menunjuk langsung ke akar, dan hal ini memberikan kinerja find diamortisasi yang mendekati O(1). Selanjutnya kita akan membahas union berdasarkan peringkat, yang menjaga pohon tetap dangkal dari atas ke bawah untuk mencapai batas invers Ackermann.

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 Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “DSU dengan Kompresi Jalur”?

Implementasikan find dengan kompresi jalur agar semua simpul di sepanjang jalur menunjuk langsung ke akar, sehingga find mencapai waktu amortisasi mendekati O(1) 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 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 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 Batas Invers Ackermann
  3. Koneksi Berlebih dan Deteksi Siklus
  4. Penggabungan Akun dan Komponen Terhubung
← Kembali ke Coding Interview Prep