Disjoint Set Union

Banyak persoalan graph dinamis berputar pada satu pertanyaan: “apakah node u dan v berada di komponen yang sama?” Kruskal butuh jawaban ini untuk setiap edge yang dipertimbangkan. Game “Minesweeper” butuh ini untuk flood-fill region. Aplikasi connectivity pada jaringan komputer juga membutuhkannya. Disjoint Set Union (DSU) — juga disebut Union-Find — adalah struktur data yang dirancang khusus untuk dua operasi: menggabungkan dua himpunan (unite) dan memeriksa apakah dua elemen berada di himpunan yang sama (find). Implementasi naif find berjalan O(n); dengan dua optimasi sakti — path compression dan union by rank — operasi find menjadi nyaris O(1) amortized, lebih tepatnya O(α(n)) dengan α inverse Ackermann yang sangat lambat tumbuh. Pada Chapter ini kita membedah DSU lebih dalam dari Chapter graph dasar, melengkapi implementasi template class yang reusable, dan menyentuh aplikasi termasuk dynamic connectivity offline.

Aturan: Himpunan Disjoint dan Dua Operasi #

DSU mengelola koleksi himpunan disjoint {S_1, S_2, ..., S_k} atas elemen {0, 1, ..., n-1}. Setiap himpunan direpresentasikan sebagai rooted tree (pohon berakar) dengan root sebagai perwakilan (representative). Edge dalam tree ini bukan edge graph asli — edge ini hanya menunjuk dari child ke parent. Dua operasi inti:

find(x): kembalikan root dari himpunan tempat x berada.
unite(a, b): gabungkan himpunan yang berisi a dengan himpunan yang berisi b bila berbeda.

Kompleksitas naif: find mengikuti rantai parent hingga root, O(n) worst case bila tree memanjang seperti linked list.

Mekanisme: Path Compression + Union by Rank #

Dua optimasi mengubah DSU dari O(n) menjadi nyaris O(1):

Path compression: saat find(x) berjalan, setiap node di sepanjang path dari x ke root di-redirect agar langsung menunjuk ke root. Operasi selanjutnya pada node-node tersebut jadi O(1).
Union by rank: saat menggabungkan dua tree, jadikan tree dengan rank lebih kecil sebagai anak dari tree dengan rank lebih besar. Rank adalah upper bound untuk tinggi tree (bukan tinggi aktual). Ini menjaga tree tetap pendek.

Kombinasi keduanya menghasilkan kompleksitas amortized O(α(n)) per operasi, dengan α = inverse Ackermann. Untuk n praktis (≤ 10^18), α(n) ≤ 4, sehingga praktis O(1).

flowchart TD A["find(7) memulai<br/>parent[7]=5, parent[5]=3, parent[3]=1, parent[1]=1"] --> B["Naik ke root: 1"] B --> C["Path compression:<br/>parent[7]=1, parent[5]=1, parent[3]=1"] C --> D["Operasi berikutnya: find(7)=1 O(1)"]

Implementasi DSU #

cpp
#include <iostream>
#include <vector>

class DSU {
public:
    explicit DSU(int n) : parent_(n), rank_(n, 0), size_(n, 1) {
        for (int i = 0; i < n; ++i) parent_[i] = i;
    }

    int find(int x) {
        if (parent_[x] != x) parent_[x] = find(parent_[x]);
        return parent_[x];
    }

    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent_[b] = a;
        size_[a] += size_[b];
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }

    bool same(int a, int b) { return find(a) == find(b); }
    int size_of(int x) { return size_[find(x)]; }

private:
    std::vector<int> parent_, rank_, size_;
};

int main() {
    DSU dsu(7);
    std::cout << "awal: same(0,3)=" << dsu.same(0, 3) << '\n';
    dsu.unite(0, 1);
    dsu.unite(1, 2);
    dsu.unite(3, 4);
    dsu.unite(2, 4);
    std::cout << "setelah unite 0-1-2 dan 3-4 dan 2-4:\n";
    std::cout << "  same(0,3)=" << dsu.same(0, 3) << '\n';
    std::cout << "  same(0,5)=" << dsu.same(0, 5) << '\n';
    std::cout << "  size_of(0)=" << dsu.size_of(0) << '\n';
    std::cout << "  size_of(5)=" << dsu.size_of(5) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
awal: same(0,3)=0
setelah unite 0-1-2 dan 3-4 dan 2-4:
  same(0,3)=1
  same(0,5)=0
  size_of(0)=5
  size_of(5)=1

Bedah Kode Baris-per-Baris #

parent_(n) dan inisialisasi parent_[i] = i: setiap elemen awalnya menjadi root dari himpunan tunggalnya sendiri. parent_[i] == i menandakan i adalah root.
rank_(n, 0): rank awal 0 untuk semua node. Rank adalah upper bound tinggi tree, bukan tinggi aktual — path compression mengubah tinggi aktual tetapi tidak menurunkan rank.
size_(n, 1): melacak ukuran setiap himpunan (opsional, berguna untuk query size_of).
find(int x) rekursif: jika parent_[x] != x, maka x bukan root. Rekursi ke find(parent_[x]) sambil assign balik ke parent_[x] — inilah path compression. Setelah pemanggilan, setiap node di path langsung menunjuk ke root.
unite: pertama-tama cari root kedua himpunan via find. Bila sama, sudah satu himpunan → return false.
if (rank_[a] < rank_[b]) std::swap(a, b): pastikan a adalah root dengan rank lebih besar (atau sama). Ini union by rank: tree kecil digantungkan ke tree besar.
parent_[b] = a: jadikan b anak dari a. Tree dengan root b kini bagian dari tree root a.
size_[a] += size_[b]: akumulasi ukuran. Hanya root yang menyimpan ukuran valid.
if (rank_[a] == rank_[b]) ++rank_[a]: rank hanya naik bila kedua root memiliki rank sama. Bila berbeda, rank tree besar tidak berubah (anaknya yang rank lebih kecil tidak menambah tinggi).
Hasil same(0,3)=1 setelah unite: rantai unite 0-1, 1-2, 3-4, 2-4 menggabungkan {0,1,2,3,4} dalam satu himpunan. size_of(0)=5 konfirmasi.
size_of(5)=1: node 5 tidak pernah di-unite, tetap himpunan tunggal.

Aplikasi: Kruskal MST #

DSU adalah tulang punggung algoritma Kruskal untuk Minimum Spanning Tree. Sortir semua edge by weight. Untuk setiap edge dari terkecil, bila kedua endpoint berbeda himpunan, gabungkan dan ambil edge. DSU memeriksa dan menggabungkan dalam O(α) per edge → total O(E log E) untuk sort + O(E · α) untuk DSU.

Aplikasi: Dynamic Connectivity Offline #

Persoalan dynamic connectivity: ada urutan operasi add_edge(u,v), remove_edge(u,v), query(u,v) (apakah u dan v terhubung?). Secara online, persoalan ini sulit (dibutuhkan struktur data kompleks seperti Euler Tour Tree, O(log² n) per operasi). Namun bila offline (semua query diketahui di awal), kita pakai Divide and Conquer on Time atau segment tree over time. Setiap edge aktif pada interval waktu tertentu — masukkan edge ke node-node segment tree yang merepresentasikan interval tersebut, lalu DFS segment tree dengan DSU yang mendukung rollback (undo operasi unite).

Rollback DSU memakai union by rank tanpa path compression (karena path compression bersifat destruktif, sulit dibatalkan). Kompleksitas O(log n) per operasi.

Kompleksitas #

Operasi	Naif	Union by rank saja	Path compression saja	Keduanya
`find`	O(n)	O(log n)	O(log n) amortized	O(α(n)) amortized
`unite`	O(n)	O(log n)	O(log n) amortized	O(α(n)) amortized

Ringkasan #

DSU mengelola koleksi himpunan disjoint dengan dua operasi: find (perwakilan himpunan) dan unite (gabung himpunan).
Path compression: setiap node di path find langsung di-redirect ke root.
Union by rank: tree kecil digantung ke tree besar untuk menjaga tree tetap pendek.
Kompleksitas amortized O(α(n)) per operasi — praktis O(1).
Memori O(n) untuk parent, rank, size.
Aplikasi: Kruskal MST, dynamic connectivity offline (dengan rollback), flood fill, Havel-Hakimi graph realization.
Untuk versi dengan rollback (undo), matikan path compression dan pakai stack operasi.