Union-find (disjoint set union): cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan union-find

Bayangkan jaringan komputer yang kabelnya ditambahkan satu per satu, dan setelah setiap kabel Anda harus menjawab "apakah komputer A dan komputer B terhubung?". Menjalankan pencarian graf untuk setiap pertanyaan butuh O(n + m) setiap kali. Union-find menjawab tiap pertanyaan dalam waktu hampir O(1) dengan memelihara grup-grup yang terhubung seiring kabel ditambahkan.

Kebutuhan yang sama muncul pada algoritma minimum spanning tree Kruskal (apakah dua ujung ini sudah berada di tree yang sama?), pada deteksi siklus di graf tak berarah, pada pengelompokan akun yang berbagi alamat email, pada simulasi perkolasi, dan pada pengolahan citra untuk memberi label pada wilayah yang terhubung.

Ide dasarnya dengan bahasa sederhana

Setiap elemen menunjuk ke sebuah parent. Elemen yang menunjuk ke dirinya sendiri adalah root, dan root adalah perwakilan seluruh grup. Untuk menemukan grup x, ikuti pointer parent sampai mencapai root. Untuk menggabungkan dua grup, cari kedua root-nya lalu buat satu root menunjuk ke yang lain.

Dua optimasi menjaga tree tetap pendek:

• Union by rank (atau by size): tempelkan tree yang lebih pendek (atau lebih kecil) di bawah yang lebih tinggi (atau lebih besar), sehingga tinggi tree hanya bertambah ketika dua tree yang sama besar digabung.
• Path compression: selama find, buat setiap node di jalur menunjuk langsung ke root, sehingga pencarian berikutnya hanya satu langkah.

Contoh langkah demi langkah: lima elemen

Mulai dengan elemen 0 sampai 4, masing-masing dalam grupnya sendiri. Array parent-nya [0, 1, 2, 3, 4]. Kita memakai union by size dan menjadikan root kedua sebagai anak ketika ukurannya sama.

Implementasi Python

Versi ini memakai union by size dan find iteratif dengan path compression, sehingga tidak ada masalah kedalaman rekursi. union mengembalikan False ketika kedua elemen sudah berada di grup yang sama, yang berguna untuk deteksi siklus.

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

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

Contoh: mendeteksi siklus di graf tak berarah

Proses edge satu per satu. Jika kedua ujung sebuah edge sudah punya root yang sama, edge itu menutup sebuah siklus. Algoritma Kruskal memakai persis pemeriksaan ini setelah mengurutkan edge berdasarkan bobot.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

Kompleksitas waktu dan ruang

α(n) adalah fungsi Ackermann invers, yang tumbuh sangat lambat sehingga paling besar 4 untuk n berapa pun yang muat di komputer nyata. Dalam praktik ini berarti waktu konstan per operasi. Robert Tarjan membuktikan batas ini pada tahun 1975. Ruangnya O(n) untuk array parent dan size.

Varian dan kesalahan umum

• Membandingkan elemen, bukan root: union harus menghubungkan find(a) dan find(b), bukan a dan b itu sendiri.
• Mengira parent[x] adalah perwakilan. Setelah beberapa union, hanya find(x) yang benar; panggil find pada setiap elemen sebelum mengelompokkan berdasarkan parent.
• find rekursif pada input besar tanpa union by rank bisa mencapai batas rekursi Python; versi iteratif di atas menghindarinya.
• Elemen yang bukan bilangan bulat 0 sampai n-1: petakan ke indeks dengan dict lebih dulu, atau simpan parent dalam dict dan tambahkan elemen secara lazy.
• Union-find tidak bisa memecah grup. Jika edge dihapus, Anda butuh struktur lain atau pendekatan offline yang memproses penghapusan secara terbalik.
• Weighted union-find menyimpan offset ke parent di setiap node, yang menjawab pertanyaan seperti "seberapa lebih berat a dibanding b?".

Kapan dipakai dan soal-soal khasnya

Gunakan union-find ketika grup hanya akan bergabung dan Anda perlu bertanya apakah dua elemen berada di grup yang sama, atau berapa banyak grup yang ada. Untuk satu pertanyaan konektivitas pada graf statis, BFS atau DFS biasa lebih sederhana. Ketika Anda butuh jalur sebenarnya, gunakan pencarian graf, karena union-find hanya tahu keanggotaan.

Soal khas: jumlah connected component, jumlah pulau (dengan sel grid sebagai elemen), redundant connection (edge yang membuat siklus), accounts merge, kepuasan persamaan kesetaraan seperti a == b, b != c, dan minimum spanning tree Kruskal.