Belajar Data Structure - Union-Find (Disjoint Set Union)

#Pendahuluan

Setelah di episode 19 kita mempelajari Kruskal's algorithm yang menggunakan Union-Find, pada episode ini kita mempelajari Union-Find (Disjoint Set Union atau DSU) secara mendalam. Union-Find adalah struktur data sederhana namun powerful yang mendukung dua operasi utama: find (menentukan set mana sebuah elemen berada) dan union (menggabungkan dua set).

Dengan optimasi path compression dan union by rank/size, Union-Find mencapai waktu hampir O(1) amortized untuk setiap operasi — salah satu contoh terbaik dari "amortized analysis" dalam ilmu komputer.

#Konsep Dasar

#Apa Itu Union-Find?

Union-Find memanage disjoint sets — kumpulan set yang tidak memiliki elemen bersamaan. Dua operasi utama:

• Find(x): menentukan representan (root) dari set yang memuat x
• Union(x, y): menggabungkan set yang memuat x dan y

#Tanpa Optimasi

Tanpa optimasi, find dan union bisa O(n) dalam kondisi terburuk — tree menjadi sangat tinggi dan miring.

#Optimasi

#Path Compression

Saat find(x), ubah parent dari setiap node di jalur menjadi root secara langsung. Ini "memperpendek" tree untuk find berikutnya.

Path compression

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

#Union by Rank

Saat union, gantung tree yang lebih pendek di bawah tree yang lebih tinggi. Ini menjaga tree tetap seimbang.

Union by rank

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1
    return True

#Union by Size

Alternatif: gantung tree yang lebih kecil (jumlah node lebih sedikit) di bawah tree yang lebih besar.

Union by size

def union_by_size(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False
    if size[rx] < size[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    size[rx] += size[ry]
    return True

#Implementasi dari Nol

Union-Find lengkap

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * 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):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.size[rx] += self.size[ry]
        self.components -= 1
        return True
 
    def connected(self, x, y):
        return self.find(x) == self.find(y)
 
    def get_size(self, x):
        return self.size[self.find(x)]

#Kompleksitas

• Find: O(α(n)) amortized — α adalah inverse Ackermann, hampir konstan (< 5 untuk input apa pun)
• Union: O(α(n)) amortized
• Space: O(n)

#Aplikasi

• Connected components: menentukan node mana yang terhubung
• Kruskal's MST: mendeteksi cycle saat menambahkan edge
• Percolation: menentukan apakah grid memiliki path dari atas ke bawah
• Dynamic connectivity: query apakah dua node terhubung setelah series union

#Praktik: Friend Circle

Friend circle problem

def find_circle_num(is_connected):
    n = len(is_connected)
    uf = UnionFind(n)
 
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                uf.union(i, j)
 
    return uf.components
 
matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
print("Friend circles:", find_circle_num(matrix))

#Penutup

Inti yang harus dibawa pulang:

• Union-Find: find (tentukan set) dan union (gabungkan set).
• Path compression: pendekkan jalur saat find → O(α(n)).
• Union by rank/size: gantung tree pendek di bawah tree tinggi.
• Kompleksitas: O(α(n)) amortized ≈ O(1) praktis.
• Aplikasi: connected components, Kruskal's MST, percolation, dynamic connectivity.

Di episode 21 selanjutnya kita akan membahas bloom filter dan count-min sketch — struktur data probabilistik yang mengorbankan akurasi sempurna untuk efisiensi memori yang luar biasa. Bloom filter memberikan O(1) insert/lookup dengan false positive tapi tidak false negative — sangat berguna untuk cache, anti-spam, dan deduplication!