PricingLoginStart free
Persediaan Temu Duga Pengaturcaraan · Pelajaran

DSU dengan Pemampatan Laluan

Laksanakan find dengan pemampatan laluan supaya semua nod pada laluan menunjuk terus kepada akar, dan mencapai find teramortisasi hampir O(1).

Pelajaran 1 daripada 413 langkah

DSU dengan Pemampatan Laluan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah DSU?

DSU, juga dikenali sebagai Gabung-Cari, ialah struktur data yang mengekalkan koleksi set yang saling terasing (tidak bertindih). Ia menyokong dua operasi teras: find (set manakah yang mengandungi unsur x?) dan union (gabungkan set yang mengandungi x dan y). DSU sesuai untuk masalah kesalinghubungan dinamik, apabila kumpulan bergabung dari semasa ke semasa tetapi tidak pernah berpecah.

Setiap unsur bermula sebagai setnya sendiri. Semasa kita memproses sisi atau hubungan, kita menggabungkan set-set tersebut. Cabarannya ialah melakukannya dengan cekap — pelaksanaan naif mengambil O(n) bagi setiap operasi, tetapi dengan pengoptimuman kita menghampiri O(1) secara purata.

# 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 dengan find Naif

Dalam DSU naif, find(x) berjalan menaiki rantai induk sehingga mencapai nod yang menunjuk kepada dirinya sendiri (akar). Jika pokok seimbang, operasi ini mengambil masa O(log n). Namun, jika kita sentiasa melakukan union dengan memautkan akar kedua di bawah akar pertama, kita boleh membentuk rantai (pokok merosot) sepanjang n, menjadikan setiap find mengambil masa O(n).

Pertimbangkan urutan union 0→1→2→3→4. Panggilan find bagi nod 0 perlu merentasi seluruh rantai. Dengan pemampatan laluan, kita menghapuskan masalah ini dengan membuat setiap nod yang dilawati menunjuk terus kepada akar semasa 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)

Pemampatan Laluan: Rekursif Satu Lintasan

Pemampatan laluan mengubah suai operasi find supaya selepas akar ditemui, setiap nod di sepanjang laluan dikemas kini untuk menunjuk terus kepada akar. Panggilan find seterusnya pada nod tersebut menjadi O(1). Versi rekursif mencapai perkara ini dengan kemas dalam satu lintasan.

Inti pentingnya ialah: selepas panggilan rekursif mengembalikan akar, kita menetapkan self.parent[x] = root sebelum mengembalikan hasil. Ini meratakan pokok — semua nod pada laluan carian kini menunjuk terus kepada akar. Hal ini tidak mengubah himpunan yang dianggotai oleh sesuatu nod; ia hanya memendekkan laluan carian pada masa hadapan.

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)

Pemampatan Laluan: Iteratif Dua Lintasan

Versi iteratif pemampatan laluan menggunakan dua lintasan: lintasan pertama bergerak ke atas untuk mencari akar; lintasan kedua melawati semula setiap nod pada laluan dan mengemas kini induknya supaya menunjuk terus kepada akar. Kaedah ini mengelakkan overhed tindanan rekursi dan selamat untuk pokok yang sangat dalam serta hampir dengan had rekursi Python.

Dalam kedua-dua pendekatan rekursif dan iteratif, kebenaran tidak berubah — find masih mengembalikan akar yang sama. Satu-satunya perbezaan ialah penunjuk induk dikemas kini sebagai kesan sampingan, menjadikan semua find seterusnya pada nod tersebut mengambil masa 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[:])

Kerumitan Teramortisasi Pemampatan Laluan

Pemampatan laluan sahaja mencapai masa teramortisasi O(log n) bagi setiap operasi sepanjang urutan m operasi. Setiap operasi find mungkin mahal pada kali pertama sesuatu rantai dilalui, tetapi operasi itu meratakan rantai tersebut supaya setiap find seterusnya pada nod berkenaan mengambil masa O(1). Jumlah kerja diagihkan merentasi banyak operasi.

Analisis formal menggunakan kaedah fungsi potensi: potensi DSU berkurang setiap kali laluan daripada nod kepada induknya dipendekkan, dan pengurangan ini membayar kos penelusuran. Tanpa union mengikut peringkat, pemampatan laluan sahaja memberikan masa teramortisasi O(log n) — sudah merupakan peningkatan besar berbanding 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')

Bilangan Komponen Bersambung

Aplikasi DSU yang lazim ialah mengira komponen bersambung dalam graf. Kita memulakan pembilang components dengan nilai n (satu bagi setiap nod). Setiap union yang berjaya (menggabungkan dua himpunan berbeza) mengurangkan pembilang sebanyak 1. Pada akhirnya, pembilang tersebut mengandungi bilangan komponen berasingan.

Kaedah ini lebih cekap daripada menjalankan BFS atau DFS untuk pertanyaan kesalinghubungan, terutamanya apabila sisi diterima secara berperingkat (dalam talian). DSU memproses setiap sisi dalam masa teramortisasi hampir O(1), tanpa mengira bila sisi itu diterima.

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: Bilangan Wilayah

Masalah Bilangan Wilayah memberikan matriks ketetanggaan n×n dan bertanya berapa banyak kumpulan bandar yang bersambung secara langsung atau tidak langsung wujud. Ini tepat merupakan masalah komponen bersambung yang dapat diselesaikan dengan kemas oleh DSU. Kita mengulangi semua pasangan (i, j) yang memenuhi isConnected[i][j] == 1 dan memanggil union(i, j).

Selepas semua hubungan diproses, dsu.components ialah jawapannya. Kaedah ini lebih ringkas dan pantas berbanding menjalankan BFS dari setiap nod yang belum dilawati, serta mengendalikan perwakilan matriks secara terus tanpa membina senarai 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 Pemampatan Laluan: Pemampatan Separuh Laluan

Selain pemampatan dua lintasan, terdapat varian satu lintasan yang lebih ringkas yang dipanggil pemampatan separuh laluan: semasa kita bergerak menaiki rantai, kita membuat setiap nod menunjuk kepada datuknya dan bukannya induknya. Kaedah ini membahagi dua panjang laluan pada setiap penelusuran tanpa lintasan kedua dan mencapai kerumitan teramortisasi O(alpha(n)) yang sama apabila digabungkan dengan union mengikut peringkat.

Pemampatan separuh laluan sering menjadi pilihan dalam pengaturcaraan kompetitif kerana kaedah ini menggunakan satu gelung yang kemas tanpa rekursi atau penelusuran kedua. Setiap langkah melaksanakan 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 Kesalinghubungan Selepas Union

Untuk memeriksa sama ada dua nod connected (dalam komponen yang sama), panggil find(x) == find(y). Jika kedua-duanya mengembalikan akar yang sama, kedua-dua nod berada dalam komponen yang sama. Inilah pertanyaan connected, dan dengan pemampatan laluan, pertanyaan ini berjalan dalam masa teramortisasi hampir O(1).

Dalam masalah temu duga, pertanyaan kesalinghubungan sering muncul secara berselang-seli dengan operasi union. DSU mengendalikan kedua-duanya secara dalam talian — anda boleh menyelang-selikan union dan pertanyaan dalam apa-apa urutan. Hal ini membezakan DSU daripada algoritma graf statik seperti BFS/DFS, yang perlu dijalankan semula selepas setiap perubahan struktur.

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

Kesilapan Lazim dalam Pelaksanaan DSU

Kesilapan yang kerap berlaku ialah memanggil find kemudian mengubah suai parent secara tidak betul. Sentiasa panggil find pada kedua-dua elemen sebelum menyemak kesamaan — jika tidak, anda mungkin membandingkan sesuatu nod dengan akarnya sendiri secara tidak betul. Kesilapan lain ialah terlupa bahawa union tidak sepatutnya melakukan apa-apa apabila kedua-dua elemen sudah berkongsi akar yang sama.

Dalam Python, had kedalaman rekursi (lalai 1000) boleh menyebabkan RecursionError bagi rantai besar yang menggunakan find rekursif. Gunakan versi iteratif dua lintasan, tingkatkan had dengan sys.setrecursionlimit, atau gunakan pemampatan separuh laluan secara iteratif untuk mengelakkan rekursi yang dalam sepenuhnya.

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

Penjejakan Saiz DSU

Dalam sesetengah masalah, anda memerlukan saiz setiap komponen, bukan sekadar akarnya. Tambahkan tatasusunan saiz yang dimulakan dengan semua nilai 1. Apabila menggabungkan dua komponen, tambahkan saiz akar yang lebih kecil kepada akar yang lebih besar. Ini membolehkan pertanyaan saiz komponen dalam masa O(1) selepas sebarang union.

Penjejakan saiz juga menjadi asas kepada union mengikut saiz (alternatif kepada union mengikut peringkat): sentiasa letakkan pokok yang lebih kecil di bawah akar pokok yang lebih besar. Ini menjamin ketinggian pokok kekal O(log n), lalu memberikan jaminan asimptotik yang sama seperti union mengikut 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

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan dalam pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini, anda telah mempelajari bahawa: DSU mengekalkan himpunan saling asing dengan operasi find dan union, pemampatan laluan meratakan pokok dengan membuat semua nod yang dilalui menunjuk terus kepada akar, dan ini memberikan prestasi find teramortisasi hampir O(1). Seterusnya, kita akan meneroka union mengikut peringkat, yang mengekalkan pokok supaya cetek dari atas ke bawah untuk mencapai had songsang Ackermann.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
90
Pelajaran
360
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “DSU dengan Pemampatan Laluan” percuma?

Ya — teks penuh “DSU dengan Pemampatan Laluan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “DSU dengan Pemampatan Laluan”?

Laksanakan find dengan pemampatan laluan supaya semua nod pada laluan menunjuk terus kepada akar, dan mencapai find teramortisasi hampir O(1). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “DSU dengan Pemampatan Laluan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. DSU dengan Pemampatan Laluan
  2. Penyatuan Mengikut Pangkat dan Had Ackermann Songsang
  3. Sambungan Berlebihan dan Pengesanan Kitaran
  4. Penggabungan Akaun dan Komponen Terhubung
← Kembali ke Persediaan Temu Duga Pengaturcaraan