Disjoint Set Union

Penulis: Polikarpus

Disjoint Set Union (Kumpulan himpunan yang tak beririsan) atau yang biasa disingkat DSU adalah struktur data yang mampu menampung sekumpulan himpunan. Tiap himpunan tidak beririsan satu sama lain, sehingga tidak ada elemen yang berada pada 2 himpunan berbeda. DSU memiliki 3 operasi utama, yaitu:

• find berguna untuk mencari sebuah perwakilan dalam himpunan

• same berguna untuk memeriksa apakah dua himpunan merupakan himpunan yang sama

• join berguna untuk menggabungkan 2 himpunan

Struktur

Dalam DSU, tiap himpunan direpresentasikan dalam sebuah pohon. Dalam pohon tersebut, akar dari pohon tersebut merupakan perwakilan dari sebuah himpunan. Perwakilan inilah yang menjadi identitas dari tiap himpunan. Sebagai contoh apabila kita memiliki himpunan {1, 2, 3}, {4},{5, 6, 7, 8}

[a] himpunan {1, 2, 3}

[b] himpunan {4}

[c] himpunan {5, 6, 7, 8}

Dalam hal ini, himpunan pertama diwakilkan oleh 2, himpunan kedua diwakilkan oleh 4, dan himpunan ketiga diwakilkan oleh 5. Terlihat bahwa untuk tiap elemen (kecuali akar) dalam himpunan akan menunjuk kepada suatu elemen lain. Apabila kita melakukan penjelajahan graf dari suatu elemen kita akan berakhir pada akar. Sebagai contoh, apabila kita melakukan penjelajahan dari node 8, kita akan berakhir pada node 5 dengan jalur 8 -> 6 -> 5

[d] Penjelajahan dari node 8 -> 6 -> 5

Hal tersebut dapat kita manfaatkan untuk melakukan operasi find dan same. Kemudian, untuk menggabungkan 2 himpunan berbeda, kita cukup untuk membuat perwakilan dari suatu himpunan untuk menunjuk kepada perwakilan himpunan lain. Sebagai contoh apabila kita memiliki himpunan {1, 2, 3} dan {6, 7, 8} , seperti pada gambar a. Apabila kita lakukan operasi join maka akan menghasilkan graf seperti pada gambar b

[e] sebelum operasi join

[f] setelah operasi join

Maka himpunan akan menjadi {1, 2, 3, 6, 7, 8}

Implementasi

Seperti yang telah dijelaskan sebelumnya, bahwa untuk tiap node pada DSU akan menunjuk kepada salah satu node lainnya. Maka dari itu untuk membuat DSU dengan N elemen, kita memerlukan sebuah array untuk menyimpan node apa yang ditunjuk oleh tiap node pada DSU. Kita akan namakan array ini parrent

Inisialisasi

Mula-mula, kita akan membuat array parrent untuk setiap node pada DSU. Kemudian, kita akan membuat semua elemen pada parrent menunjuk kepada dirinya sendiri. Hal ini dikarenakan pada awalnya, semua elemen merupakan merupakan himpunan yang berbeda satu sama lain. Sehingga kita hanya perlu gunakan parent[i] = i untuk setiap indeks i. Berikut implementasinya

int parent[N + 1]; // buat array parent

int main(){    
    for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
        parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
    }
}

[g] Himpunan mula-mula

Operasi Find

Seperti yang sudah dijelaskan, operasi find berguna untuk mencari perwakilan dari suatu himpunan. Untuk melakukannya, kita dapat memanfaatkan prinsip rekursif dimana apabila node sekarang adalah perwakilan / akar (ditandai dengan parent dari node itu adalah dirinya sendiri) maka kita akan menggunakan node kita sebagai jawaban. Sedangkan apabila node sekarang bukan perwakilan, maka kita akan melanjutkan rekursi kepada parent dari node sekarang. Operasi ini memilki kompleksitas sebesar O(log N) dimana N adalah banyaknya anggota himpunan. Mengapa log N ?, hal ini dikarenakan semisal untuk tiap node memiliki anak sebanyak 2, maka total jarak suatu node kepada perwakilannya adalah sekitar log N . Berikut adalah contoh implementasinya

int find(int node){
    if (parent[node] == node){
        /* Apabila node sekarang adalah perwakilan, maka kita
        akan mengembalikan nilai node */
        return node;
    }
    else{
        /* Melakukan rekursi kepada node parent
        apabila node sekarang bukan perwakilan */
        return find(parent[node]);
    }
}

Operasi Same

Untuk memeriksa apakah 2 himpunan merupakan himpunan yang sama, kita hanya perlu memeriksa perwakilan dari kedua himpunan saja. Apabila perwakilan dari kedua himpunan sama, maka dapat dipastikan bahwa kedua himpunan itu sama. Begitupun sebaliknya.

bool same(int a, int b){
    // memerika apakah node a dan b memiliki perwakilan yang sama
    return find(a) == find(b);
}

Operasi Join

Untuk menggabungkan dua himpunan, maka kita cukup mencari perwakilan dari kedua himpunan, lalu membuat salah satu dari kedua perwakilan menunjuk kepada perwakilan yang lain. Berikut adalah implementasinya.

void join(int a, int b){
    a = find(a); // mencari perwakilan node a
    b = find(b); // mencari perwakilan node b
    
    // buat node a menunjuk node b
    parent[a] = b;
}

Operasi join memiliki kompleksitas sebanyak O(log N) dikarenakan ia memanggil fungsi find dengan kompleksitas O(log N) sebanyak 2 kali

Optimasi

Terkadang, DSU yang kita buat akan berbentuk garis lurus seperti ini.

[H] DSU kasus terburuk dimana graf berbentuk lutus

Sehingga, apabila kita melakukan pemanggilan find(N) , hal itu akan membuat operasi find akan berjalan sebanyak N kali rekursif dikarenakan kita mengunjungi semua node yang ada selama pencarian perwakilan dari himpunan. Sehingga alih-alih O(log N) , kompleksitas program menjadi menyerupai O (N) . Oleh karena itu, kita perlu suatu cara untuk mempercepat eksekusi DSU yang kita miliki

Path Compression

Salah satu cara untuk mengoptimasi DSU yang kita miliki adalah dengan melakukan kompresi pada setiap path dalam DSU. Sebagai contoh apabila kita memiliki suatu DSU pada gambar [h]

Tampak bahwa apabila kita memanggil find(4) kita akan melakukan rekursi sebanyak 4 kali. Untuk mengoptimalkannya, kita dapat memperpendek panjang path dari node 4 hingga node 1 dengan cara membuat node 4 langsung menunjuk kepada node 1 di akhir fungsi find . Begitu pun dengan semua node yang kita lalui saat melakukan perjalanan dari node 4. Kita akan membuat semua node di dalam path langsung menunjuk kepada node 1. Dengan begitu apabila suatu saat kita memanggil kembali fungsi find(4), maka kompleksitas dari fungsi tersebut menjadi O(1) karena kita dapat langsung menuju kepada node 1 dengan satu langkah. Meskipun secara rata-rata, algoritma ini tetap bekerja dengan kecepatan O(log N) . Sehinnga, DSU akan berubah menjadi seperti gambar [i]

[i] DSU hasil path compression

Berikut adalah implementasi dari path compression

int find(int node){
    if(parent[node] == node) return node;
    else{
        // parent dari node sekarang akan menunjuk langsung kepada perwakilan
        parent[node] = find(parent[node]);
        return parent[node];
    }
}

Union by Size

Cara kedua yang dapat dilakukan untuk mempercepat DSU yang kita miliki adalah dengan melakukan penggabungan dua himpunan dengan memperhatikan ukuran (banyak node yang ada di masing-masing himpunan) dari tiap himpunan. Secara intuitif, kita menginginkan agar path terpanjang yang ada di DSU kita sependek mungkin. Jika dipikirkan secara greedy, kita dapat mencapai kondisi itu dengan cara membuat perwakilan dari himpunan yang lebih kecil langsung menunjuk kepada perwakilan himpunan yang lebih besar. Mengapa demikian? Karena untuk suatu himpunan yang memiliki ukuran lebih besar, maka kemungkinan besar dia akan memiliki path terpanjang yang lebih panjang pula dari path terpanjang milik himpunan yang lebih kecil. Dengan begitu, kita berharap bahwa path terpanjang yang kita miliki di himpunan baru menjadi sama saja dengan path terpanjang himpunan besar

[j] sebelum join

[k] graf kanan dibuat menunjuk kepada graf kiri dikarenakan ukuran dari graf kiri lebih besardari ukuran graf kanan

Berikut adalah implementasi dari Union by Size

int parent[N + 1]; // buat array parent
int size[N + 1];   // untuk menyimpan ukuran suatu himpunan

int main(){    
    for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
        parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
        size[i]  = 1; // ukuran mula-mula tiap himpunan adalah 1
    }
}

Berikut adalah operasi join yang kita modifikasi sedikit

void join(int a, int b){
    a = find(a);
    b = find(b);
    
    if(size[a] < size[b]){
        /* membuat a selalu menjadi himpunan yang lebih besar dari b,
        hal ini untuk kemudahan penulisan program selanjutnya */
        swap(a, b); 
    }
    
    // tambahkan ukuran dari b kepada a
    size[a] += size[b];
    
    // buat node b menunjuk kepada a sebagai perwakilan
    parent[b] = a;
}

Union by Depth

Mirip dengan Union by Size, namun kita akan menggabungkan 2 himpunan berdasarkan kedalaman (panjang path) terpanjang dari 2 himpunan. Apabila kita memiliki 2 himpunan, maka perwakilan dari himpunan dengan kedalaman yang lebih pendek, akan kita buat langsung menunjuk kepada perwakilan dari himpunan dengan kedalaman yang lebih panjang. Dengan begitu, kedalaman dari himpunan baru tidak akan berubah dari kedalaman 2 himpunan sebelumnya. Namun untuk kasus kedalaman kedua himpunan sama, maka kedalaman dari himpunan baru akan memiliki ukuran sama dengan kedalaman dari himpunan lama + 1. Berikut adalah ilustrasinya

[l] graf mula-mula

[m] himpunan kiri dibuat menunjuk himpunan kanan, karena himpunan kiri memiliki kedalaman 2 sementara himpunan kanan memiliki kedalaman 3 (kedalaman kiri < kedalaman kanan)

Berikut adalah implementasi dari Union by Depth

int parent[N + 1]; // buat array parent
int depth[N + 1];  // untuk menyimpan kedalaman suatu himpunan

int main(){    
    for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
        parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
        depth[i]  = 0; // kedalaman mula-mula tiap himpunan adalah 0
    }
}

Berikut adalah operasi join yang kita modifikasi sedikit

void join(int a, int b){
    a = find(a);
    b = find(b);
    
    if(depth[a] < depth[b]){
        /* membuat a selalu menjadi himpunan yang memiliki kedalaman maksimal lebih
        dari b, hal ini untuk kemudahan penulisan program selanjutnya */
        swap(a, b); 
    }
    
    if(depth[a] == depth[b]){
        /* apabila kedalaman mula-mula dari himpunan a, maka kedalaman maksimal dari a
        akan bertambah 1 (karena ditambah dari kedalaman maksimal dari b) */
        depth[a]++;
    }
    
    // buat node b menunjuk kepada a sebagai perwakilan
    parent[b] = a;
}

Baik Union by Size / Union by Depth akan menghasilkan DSU dengan kompleksitas operasi find dan join masing masing O(log N) . Hal ini tentu sangat baik mengingat kompleksitas O (log N) tergolong cepat.

Kita telah mengenal 3 cara berbeda dalam mengoptimasi DSU yang kita miliki. Dalam penerapannya, ketiga algoritma tadi dapat dikombinasikan satu dengan yang lainnya agar dapat tercapai DSU yang kita inginkan

Sumber	Nama Soal	Tingkat Kesulitan	Tingkat Kesulitan
TLX TOKI	Membangun Jalan Antar Kandang	Mudah	Indonesia