Disjoint Set Union

Masalah berulang di graph: “apakah vertex u dan v berada dalam komponen yang sama?” Menjalankan BFS/DFS setiap query membutuhkan O(V+E) — terlalu lambat untuk banyak query. Disjoint Set Union (DSU), juga dikenal sebagai Union-Find, menyelesaikan masalah ini dengan kompleksitas hampir O(1) per operasi (amortized, dengan path compression dan union by rank). DSU adalah struktur data incremental: kita mulai dengan V himpunan singletons, lalu menggabungkan himpunan saat edge baru ditambahkan. Pada Chapter ini kita akan mengimplementasikan DSU sebagai template class, menganalisis dua optimasi utama (path compression dan union by rank), dan mengaplikasikannya pada Kruskal’s algorithm.

Definisi DSU #

DSU adalah struktur data yang menyimpan partisi dari himpunan {0, 1, ..., n-1} menjadi beberapa himpunan disjoint. Dukungan tiga operasi:

MakeSet(x) — buat himpunan baru berisi hanya x. Biasanya dilakukan saat inisialisasi.
Find(x) — kembalikan representative (root) himpunan yang berisi x.
Union(x, y) — gabungkan himpunan yang berisi x dan y menjadi satu himpunan. Bila sudah satu himpunan, tidak ada perubahan.

Implementasi naive memakai array parent[x] yang menyimpan parent langsung dari x. Find(x) menelusuri parent hingga root (vertex dengan parent[x] == x). Kompleksitas O(n) per operasi pada worst case.

Dua Optimasi Utama #

Path Compression #

Saat Find(x) menelusuri path dari x ke root, kita menulis ulang parent setiap vertex di path agar langsung menunjuk ke root. Operasi berikutnya pada vertex yang sama menjadi O(1).

flowchart TD A1[5] --> B1[4] --> C1[3] --> D1[2] --> E1[1] --> F1[0 root] A2[5] --> F2[0 root] B2[4] --> F2 C2[3] --> F2 D2[2] --> F2 E2[1] --> F2

Pada gambar kiri, Find(5) menelusuri path 5 → 4 → 3 → 2 → 1 → 0. Pada gambar kanan (setelah path compression), seluruh vertex pada path langsung menunjuk ke root 0.

Union by Rank #

Saat menggabungkan dua himpunan, jadikan root dengan rank lebih besar sebagai parent dari root dengan rank lebih kecil. Rank adalah estimasi kedalaman tree — meningkat hanya saat dua tree dengan rank sama digabung.

Tanpa optimasi, Union dapat menghasilkan linked list dengan Find O(n). Dengan kedua optimasi, kompleksitas amortized O(α(n)) di mana α adalah inverse Ackermann — praktis konstan untuk n realistis.

Implementasi Template Class #

Kode: DSU dengan Path Compression + Union by Rank #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

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;  // setiap vertex adalah root sendiri
    }

    // Find dengan path compression
    int find(int x) {
        if (parent_[x] != x) {
            parent_[x] = find(parent_[x]);   // compress: langsung ke root
        }
        return parent_[x];
    }

    // Union by rank; return true bila dua set berbeda digabung, false bila sudah satu set
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;        // ra jadi parent rb
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        size_[ra] += size_[rb];
        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_;
    std::vector<int> rank_;
    std::vector<int> size_;
};

int main() {
    DSU dsu(10);  // 10 vertex: {0,1,...,9} masing-masing singleton

    // Gabungkan beberapa set
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    dsu.unite(4, 5);
    dsu.unite(1, 3);   // gabung {0,1} dengan {2,3} -> {0,1,2,3}
    dsu.unite(5, 0);   // gabung {4,5} dengan {0,1,2,3} -> {0,1,2,3,4,5}

    // Cek keanggotaan
    std::cout << "Cek keanggotaan:\n";
    std::cout << "  same(0, 5) = " << dsu.same(0, 5) << "  (harusnya 1)\n";
    std::cout << "  same(0, 6) = " << dsu.same(0, 6) << "  (harusnya 0)\n";
    std::cout << "  same(2, 4) = " << dsu.same(2, 4) << "  (harusnya 1)\n";
    std::cout << "  same(6, 7) = " << dsu.same(6, 7) << "  (harusnya 0)\n";

    // Ukuran setiap set
    std::cout << "\nUkuran set:\n";
    std::cout << "  size(find(0)) = " << dsu.size_of(0) << '\n';
    std::cout << "  size(find(6)) = " << dsu.size_of(6) << '\n';
    std::cout << "  size(find(8)) = " << dsu.size_of(8) << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Cek keanggotaan:
  same(0, 5) = 1  (harusnya 1)
  same(0, 6) = 0  (harusnya 0)
  same(2, 4) = 1  (harusnya 1)
  same(6, 7) = 0  (harusnya 0)

Ukuran set:
  size(find(0)) = 6
  size(find(6)) = 1
  size(find(8)) = 1

Baris explicit DSU(int n) : parent_(n), rank_(n, 0), size_(n, 1): inisialisasi parent_[i] = i (setiap vertex root dirinya sendiri), rank_[i] = 0, size_[i] = 1.
Baris parent_[x] = find(parent_[x]); dalam find(): inilah path compression. Saat rekursi ke parent, kita assign hasil kembali ke parent_[x]. Setelah panggilan ini, x langsung menunjuk ke root.
Baris if (rank_[ra] < rank_[rb]) std::swap(ra, rb);: pastikan ra selalu menjadi root dengan rank ≥ rb. Root dengan rank lebih besar menjadi parent dari yang lebih kecil.
Baris if (rank_[ra] == rank_[rb]) rank_[ra]++;: bila rank sama, rank hasil gabungan naik 1.
Baris size_[ra] += size_[rb];: update ukuran set. Berguna untuk query “berapa anggota set x?”.
Hasil same(0, 5) = 1: setelah unite(0,1), unite(2,3), unite(4,5), unite(1,3), unite(5,0), vertex 0 dan 5 berada dalam satu set {0,1,2,3,4,5}.
Hasil size(find(0)) = 6: set yang berisi 0 punya 6 anggota. Ukuran set lainnya (vertex 6, 7, 8, 9) masih 1 karena tidak pernah di-unite.

Aplikasi: Kruskal’s MST (Preview Lengkap) #

Pada Chapter Edge List, kita sudah melihat preview Kruskal. Sekarang kita akan menyusun ulang dengan DSU lengkap dan analisis tuntas.

Kode: Kruskal dengan DSU #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& o) const {
        if (w != o.w) return w < o.w;
        return std::make_pair(u, v) < std::make_pair(o.u, o.v);
    }
};

class DSU {
public:
    explicit DSU(int n) : parent_(n), rank_(n, 0) {
        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) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
private:
    std::vector<int> parent_, rank_;
};

int main() {
    // Graph undirected weighted: 5 vertex, 7 edge
    std::vector<Edge> edges = {
        {0, 1, 4}, {0, 2, 1}, {1, 2, 2},
        {1, 3, 5}, {2, 3, 2}, {2, 4, 6}, {3, 4, 3}
    };
    const int V = 5;

    // Kruskal: sort edge ascending by weight, lalu unite selama tidak membentuk cycle
    std::sort(edges.begin(), edges.end());

    DSU dsu(V);
    long long total_cost = 0;
    int edges_used = 0;
    std::vector<Edge> mst;

    std::cout << "Langkah Kruskal:\n";
    for (const auto& e : edges) {
        bool added = dsu.unite(e.u, e.v);
        std::cout << "  Edge (" << e.u << "-" << e.v << ", w=" << e.w << "): "
                  << (added ? "DITAMBAHKAN" : "dilewati (cycle)") << '\n';
        if (added) {
            mst.push_back(e);
            total_cost += e.w;
            edges_used++;
            if (edges_used == V - 1) break;
        }
    }

    std::cout << "\nMST edges:\n";
    for (const auto& e : mst) {
        std::cout << "  (" << e.u << ", " << e.v << ", w=" << e.w << ")\n";
    }
    std::cout << "Total MST cost = " << total_cost << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Langkah Kruskal:
  Edge (0-2, w=1): DITAMBAHKAN
  Edge (1-2, w=2): DITAMBAHKAN
  Edge (2-3, w=2): DITAMBAHKAN
  Edge (3-4, w=3): DITAMBAHKAN

MST edges:
  (0, 2, w=1)
  (1, 2, w=2)
  (2, 3, w=2)
  (3, 4, w=3)
Total MST cost = 8

Baris bool added = dsu.unite(e.u, e.v);: coba gabungkan set e.u dan e.v. Bila berhasil (return true), edge ditambahkan ke MST. Bila gagal (return false), kedua vertex sudah satu set — edge ini akan membentuk cycle, dilewati.
Hasil sort: edge diurutkan ascending by weight: 0-2 (w=1), 1-2 (w=2), 2-3 (w=2), 3-4 (w=3), 0-1 (w=4), 1-3 (w=5), 2-4 (w=6).
Edge 0-2 (w=1) ditambahkan: set {0} dan {2} digabung → {0,2}.
Edge 1-2 (w=2) ditambahkan: set {1} dan {0,2} digabung → {0,1,2}.
Edge 2-3 (w=2) ditambahkan: set {0,1,2} dan {3} digabung → {0,1,2,3}.
Edge 3-4 (w=3) ditambahkan: set {0,1,2,3} dan {4} digabung → {0,1,2,3,4}. MST lengkap (V-1 = 4 edge), loop berhenti via if (edges_used == V - 1) break;.
Edge 0-1 (w=4) tidak diproses: loop sudah berhenti. Bila break dihapus, edge ini akan ditolak dengan pesan “dilewati (cycle)” karena vertex 0 dan 1 sudah satu set.
Hasil MST cost = 1+2+2+3 = 8: bobot minimum untuk menghubungkan seluruh 5 vertex.

Aplikasi Lain #

Dynamic Connectivity #

DSU unggul untuk masalah incremental connectivity: edge hanya ditambah, tidak dihapus. Query “apakah u dan v connected?” dijawab dengan same(u, v).

Tambah edge (u, v): unite(u, v) — O(α(n)).
Query connected: same(u, v) — O(α(n)).

Untuk masalah dengan deletion edge (dynamic graph dengan delete), DSU tidak cukup — diperlukan struktur lebih kompleks seperti link-cut tree atau offline processing.

Cycle Detection pada Undirected Graph (Alternative) #

Pada Chapter Cycle Detection, kita menggunakan DFS dengan parent tracking. Alternatif: untuk setiap edge {u, v}, cek apakah same(u, v) bila sudah true → cycle. Bila false → unite(u, v).

Menghitung Connected Components #

Awalnya V komponen (semua singleton). Setiap unite yang berhasil mengurangi jumlah komponen sebanyak 1. Counter komponen = V - jumlah_unite_berhasil.

Kode: Hitung Connected Components dengan DSU #

cpp
#include <iostream>
#include <vector>

class DSU {
public:
    explicit DSU(int n) : parent_(n), rank_(n, 0) {
        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) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
private:
    std::vector<int> parent_, rank_;
};

int main() {
    // Graph: 7 vertex, 5 edge (3 komponen)
    std::vector<std::pair<int,int>> edges = {
        {0, 1}, {0, 2}, {1, 2},  // komponen 1: {0,1,2}
        {3, 4}, {4, 5}           // komponen 2: {3,4,5}
        // vertex 6 isolated
    };
    const int V = 7;

    DSU dsu(V);
    int components = V;
    for (auto [u, v] : edges) {
        if (dsu.unite(u, v)) components--;
    }
    std::cout << "Jumlah connected components = " << components << '\n';

    // List komponen
    std::vector<std::vector<int>> groups(V);
    for (int v = 0; v < V; ++v) groups[dsu.find(v)].push_back(v);
    int shown = 0;
    std::cout << "Komponen:\n";
    for (int i = 0; i < V; ++i) {
        if (!groups[i].empty()) {
            std::cout << "  Komponen " << (shown++) << ":";
            for (int v : groups[i]) std::cout << " " << v;
            std::cout << '\n';
        }
    }
    return 0;
}

Output yang Dihasilkan:

text
Jumlah connected components = 3
Komponen:
  Komponen 0: 0 1 2
  Komponen 1: 3 4 5
  Komponen 2: 6

Baris int components = V;: awalnya V komponen (semua singleton).
Baris if (dsu.unite(u, v)) components--;: setiap unite yang berhasil menggabungkan dua komponen berbeda mengurangi counter. Catatan: bila edge (u, v) di mana u dan v sudah satu set, unite return false → counter tidak berkurang.
Baris groups[dsu.find(v)].push_back(v);: kelompokkan vertex berdasarkan root-nya. Hanya root akan punya groups[i] tidak kosong.
Hasil 3 komponen: sesuai ekspektasi — {0,1,2}, {3,4,5}, {6}.

Kompleksitas dan Perbandingan #

Aspek	DSU	BFS/DFS untuk connected components
Inisialisasi	O(V)	O(V)
Tambah edge	O(α(n))	— (harus rebuild)
Cek connected	O(α(n))	O(V+E) per query
Hapus edge	Tidak didukung	— (harus rebuild)
Cocok untuk	Online edge insertion	Static graph
Memori	O(V)	O(V+E) (adj list)

Ringkasan #

DSU menyimpan partisi himpunan {0..n-1} dengan operasi MakeSet, Find, Union.
Dua optimasi: path compression (di Find) dan union by rank (di Union).
Kompleksitas amortized O(α(n)) per operasi — praktis O(1) untuk n realistis.
Aplikasi utama: Kruskal’s MST, incremental connectivity, cycle detection alternatif, hitung connected components.
DSU hanya mendukung edge addition; untuk edge deletion, gunakan struktur lain atau offline processing.
Implementasi sebagai template class dengan field parent_, rank_, size_ adalah idiom standar C++.