My first Magazine pemrograman-kompetitif-dasar | Page 113

10
Struktur Data NonLinear
Struktur data tidak harus selalu menyimpan data pada sebuah rantai lurus. Terdapat pula
struktur data yang menyimpan datanya pada struktur bercabang yang memungkinkan pelaksanaan
suatu operasi secara efisien. Pada bagian ini, kita akan mempelajari struktur data disjoint set
dan heap .
10.1
Disjoint Set
Disjoint set merupakan struktur data yang efisien untuk mengelompokkan elemen-elemen
secara bertahap. Disjoint set mendukung operasi join, yaitu menggabungkan kelompok dari
sepasang elemen. Operasi lain yang didukung adalah check, yaitu memeriksa apakah sepasang
elemen berada di kelompok yang sama. Sebagai motivasi, perhatikan contoh soal berikut:
Contoh Soal 10.1: Membangun Jalan Antar Kandang
Pak Dengklek memiliki N kandang bebek yang tersebar di peternakannya, dinomori dari 1
sampai dengan N. Setiap pagi, Pak Dengklek akan mengunjungi satu per satu kandang dan
memberi makan bebek-bebeknya.
Berhubung musim hujan telah tiba, tanah di peternakan Pak Dengklek menjadi becek dan
perjalanan antar kandang ke kandang menjadi tidak nyaman. Untuk mengatasi masalah
ini, Pak Dengklek berencana membangun jalan setapak yang menghubungkan kandang-
kandangnya.
Dalam merencanakan pembangunan jalan ini, Pak Dengklek meminta bantuan Anda untuk
melaksanakan sejumlah operasi. Setiap operasi dapat berbentuk salah satu dari:
• join(a, b), artinya Pak Dengklek akan membangun jalan yang menghubungkan kandang
a dengan kandang b. Kini seseorang dapat berpindah dari kandang a ke kandang b
(dan sebaliknya) dengan jalan ini.
• check(a, b), artinya Pak Dengklek ingin mengetahui apakah kandang a dan kandang b
terhubung?
Pak Dengklek mendefinisikan dua kandang dikatakan terhubung apabila seseorang yang
berada di kandang a dapat berpindah ke kandang b dengan menggunakan serangkaian jalan
setapak (boleh nol).
Bantulah Pak Dengklek dalam melaksanakan operasi-operasi tersebut!
Kita dapat merepresentasikan kandang-kandang yang saling terhubung oleh serangkaian
jalan dengan himpunan. Pada awalnya, setiap kandang terhubung hanya dengan dirinya sendiri,
jadi setiap kandang membentuk himpunannya masing-masing. Ketika terdapat pembangunan jalan
103