Struktur DataMenengahFase D–FE1E5

Union-Find

Union-Find (Disjoint Set) melacak pengelompokan yang terus berubah dengan sangat cepat. Operasi UNION menggabungkan dua kelompok menjadi satu; operasi FIND menelusuri induk sebuah anggota sampai ke akar kelompoknya. Dua anggota terhubung bila akarnya sama. Dengan trik union-by-rank dan path-compression, keduanya nyaris seketika. Visualisasi menggabungkan orang menjadi lingkaran pertemanan lalu menjawab apakah dua orang terhubung.

Contoh kasus

Menentukan apakah dua orang berada di lingkaran pertemanan yang sama di media sosial, atau apakah dua titik terhubung dalam satu jaringan.

Silabus

Tiap kelompok punya satu akar; dua anggota terhubung bila akarnya sama. UNION menggabung, FIND menelusuri akar.

Tujuan Belajar

·Memahami struktur himpunan-terpisah (disjoint set)
·Menjelaskan operasi UNION dan FIND
·Mengaitkan dengan konektivitas jaringan dan pertemanan

Cara Kerja

·Awalnya tiap orang adalah kelompoknya sendiri.
·UNION(a, b): sambungkan akar satu kelompok ke akar kelompok lain.
·FIND(x): telusuri induk x sampai ke akar kelompoknya.
·Dua orang terhubung bila FIND(a) == FIND(b).

Prasyarat

·Konsep pointer / induk
·Pohon sederhana
·Perbandingan

Contoh Nyata

·Cek apakah dua orang satu lingkaran pertemanan di media sosial.
·Deteksi komponen terhubung dalam jaringan.
·Dipakai algoritma Kruskal untuk membangun jaringan termurah.

Kompleksitas hampir O(1) per operasi (dengan path-compression)