Union-Find (Disjoint Set) — Struktur Data

Union-Find (juga dikenal sebagai Disjoint Set Union atau DSU) adalah struktur data yang melacak sekumpulan elemen yang terbagi dalam beberapa set yang tidak…

Union-find (juga disebut disjoint set) menyimpan beberapa kelompok yang gak saling tumpang tindih, dan menjawab dua hal dengan cepat: "dua orang ini satu kelompok gak?" dan "gabungkan kelompok mereka". Bayangkan kelompok pertemanan: awalnya tiap orang sendirian, lalu tiap kali dua orang berkenalan, kelompok mereka bergabung jadi satu.

🧪 Tebakan cepat: ada 5 orang, nomor 0 sampai 4. Orang 0 berkenalan dengan 1, lalu 2 berkenalan dengan 3. Sekarang ada berapa kelompok? Tebak dulu, jawabannya ada di bagian "Tiap kelompok punya ketua".

Tiap kelompok punya ketua

Tiap orang menunjuk ke satu orang di kelompoknya, namanya parent. Ikuti parent terus ke atas, kamu sampai di ketua kelompok (root): orang yang parent-nya dirinya sendiri. Dua orang satu kelompok kalau ketuanya sama.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // [0, 1, 2, ...]
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // naik sampai ketua
    return x;
  }

  union(a, b) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false; // sudah satu kelompok
    this.parent[rb] = ra;        // ketua b sekarang ikut ketua a
    return true;
  }

  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

this.parent adalah array: index-nya nomor orang, isinya nomor parent-nya. Array.from({ length: n }, (_, i) => i) bikin [0, 1, 2, ..., n - 1], jadi awalnya tiap orang jadi ketua dirinya sendiri.
find(x) naik lewat parent sampai ketemu orang yang parent-nya dirinya sendiri, lalu mengembalikan ketua itu.
union(a, b) mencari ketua keduanya. Kalau beda, ketua b dipasang di bawah ketua a. Cukup ketuanya yang dipindah: anggota lain ikut, karena jalan mereka ke atas lewat ketua lama.
connected(a, b) membandingkan ketua: sama berarti satu kelompok.

Begini jalannya dengan 5 orang:

Langkah	`parent`	Kelompok
awal	`[0, 1, 2, 3, 4]`	5: {0} {1} {2} {3} {4}
`union(0, 1)`	`[0, 0, 2, 3, 4]`	4: ketua 1 dipasang di bawah 0
`union(2, 3)`	`[0, 0, 2, 2, 4]`	3: {0, 1} {2, 3} {4}
`union(1, 2)`	`[0, 0, 0, 2, 4]`	2: ketua 1 adalah 0, ketua 2 adalah 2, jadi 2 dipasang di bawah 0

Jawaban tebakan: setelah dua union pertama ada 3 kelompok. Setelah union(1, 2), find(3) naik dari 3 ke 2 lalu ke 0, jadi ketua 3 sekarang 0, sama dengan ketua 1.

Menghitung kelompok

Tiap kelompok punya tepat satu ketua. Jadi jumlah kelompok sama dengan jumlah orang yang parent-nya dirinya sendiri. Di [0, 0, 0, 2, 4] ketuanya 0 dan 4: ada 2 kelompok. Di kode: loop lewat semua index, dan hitung yang this.parent[i] === i.

Biar tetap cepat

Kalau apes, union bisa membentuk rantai panjang (0 di bawah 1, 1 di bawah 2, dan seterusnya), dan find harus naik satu per satu. Itu O(n): datanya dua kali lipat, waktunya kira-kira dua kali lipat. Dua perbaikan mencegahnya:

Union by rank: waktu menggabung, pohon yang lebih pendek dipasang di bawah pohon yang lebih tinggi, jadi pohonnya tetap pendek.
Path compression: waktu find naik ke ketua, semua orang yang dilewati langsung dipasang ke ketua, jadi find berikutnya cuma satu langkah.

Dengan keduanya sekaligus, find dan union jadi hampir O(1): rata-rata per operasi, dihitung dari banyak operasi berturut-turut, waktunya hampir tetap berapa pun jumlah datanya. Latihan gak memerlukan keduanya; versi sederhana di atas sudah cukup.

Dipakai di mana

Union-find cocok kalau pertanyaannya "di kelompok mana?" dan kelompoknya cuma digabung, gak pernah dipecah. Contohnya menghitung kelompok teman, mengecek apakah dua komputer di jaringan tersambung, dan algoritma Kruskal. Kruskal mencari minimum spanning tree: kumpulan jalan paling murah yang menyambung semua kota. Sebelum menambah jalan, dia bertanya ke union-find apakah dua kotanya sudah tersambung; kalau sudah, jalan itu dilewati supaya gak ada putaran.

💡 Path compression dan union by rank di kode

// di constructor: this.rank = new Array(n).fill(0);

find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]); // pasang langsung ke ketua
  }
  return this.parent[x];
}

union(a, b) {
  let ra = this.find(a);
  let rb = this.find(b);
  if (ra === rb) return false;
  if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra]; // yang lebih pendek di bawah
  this.parent[rb] = ra;
  if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
  return true;
}

rank adalah perkiraan tinggi pohon tiap ketua. find versi ini rekursif: sambil kembali dari ketua, tiap orang di jalurnya langsung diarahkan ke ketua.

⚠️ Jebakan yang sering ketemu

Membandingkan parent, bukan ketua. Di [0, 0, 0, 2, 4], parent 3 adalah 2, padahal ketuanya 0. Selalu bandingkan hasil find.
Memindah orangnya, bukan ketuanya. this.parent[b] = a tanpa find memutus b dari kelompok lamanya, dan anggota lain tertinggal. Pasang ketua di bawah ketua.
Menulis jumlah kelompok langsung. countComponents harus menghitung dari array parent, karena class-nya juga dites dengan urutan union lain.
Butuh memecah kelompok? Union-find cuma bisa menggabung. Kalau kelompok perlu dipisah lagi, pakai struktur lain.

TL;DR: Union-find menyimpan kelompok sebagai array parent. Ketua (root) adalah orang yang parent-nya dirinya sendiri. find(x) naik sampai ketua, union(a, b) memasang ketua yang satu di bawah ketua yang lain, dan dua orang satu kelompok kalau ketuanya sama. Jumlah kelompok sama dengan jumlah ketua. Path compression plus union by rank membuat operasinya hampir O(1). Kruskal memakai union-find untuk menghindari putaran.