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

Bayangkan kamu punya 10 orang, dan ingin cepat menjawab dua pertanyaan:

1. "Apakah si A dan si B ada di grup yang sama?"
2. "Gabungkan grup si A dan grup si B."

Union-Find menjawab keduanya dalam waktu hampir O(1) (secara teknis α(n) — inverse Ackermann, praktis konstan).

Dua operasi utama

Dua elemen berada di set yang sama jika dan hanya jika find(x) === find(y).

Representasi: forest of trees

Setiap set direpresentasikan sebagai pohon terbalik — setiap node menunjuk ke parent-nya. Root adalah node yang parent-nya diri sendiri.

class UnionFind {
  constructor(n) {
    // Awalnya setiap elemen jadi root sendiri
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0); // perkiraan tinggi subtree
    this.count = n; // jumlah komponen terpisah
  }

  // find dengan path compression
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // flatten saat traversal
    }
    return this.parent[x];
  }

  // union dengan union by rank
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // sudah di set yang sama

    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    this.count--;
    return true;
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

Dua optimasi kunci

• Path compression pada find: setiap node yang dilalui langsung dipointing ke root. Traversal berikutnya jadi instan.
• Union by rank pada union: pohon lebih pendek digantung di pohon lebih tinggi, jaga agar tree tetap rata.

Dengan keduanya, amortized cost per operasi = O(α(n)), di mana α(n) ≤ 4 untuk semua n yang mungkin dipakai di praktik.

Kegunaan nyata

Rule of thumb: Kalau pertanyaannya "di grup mana?" atau "gabungkan grup", dan jarang perlu memisah kembali — Union-Find biasanya adalah jawaban optimal.

🎭 Analogi sehari-hari: Lomba balap kelompok di kampung. Awalnya tiap orang grup sendiri. Lalu pelan-pelan grup gabung. Pertanyaan tiap saat: "Saya satu grup sama Budi gak?" Daripada cek satu per satu (lambat), tiap grup punya ketua (root). Cek "ketua kita sama gak?" — kalau iya, satu grup. Kalau gabung 2 grup, ketua salah satu jadi anak ketua satunya. Itulah Union-Find.

💡 Kenapa α(n) ≤ 4? Inverse Ackermann tumbuh sangat lambat — bahkan untuk n = jumlah atom alam semesta, α(n) cuma ~4. Jadi praktiknya Union-Find ≈ O(1), tapi bukan benar-benar konstan secara matematik.

⚠️ Jebakan umum:

• Tanpa path compression = find jadi O(n) di tree miring. Wajib pakai
• Tanpa union by rank/size = bisa terbentuk linked list panjang
• find rekursif di n besar = stack overflow. Iteratif lebih aman
• Butuh "split" grup? Union-Find tidak support — pakai struktur lain (segment tree, dll)

🎯 Union-Find vs BFS untuk komponen:

• Graph yang statis (sekali bangun) → BFS/DFS (O(V+E) sekali jalan)
• Graph yang dinamis (banyak union/query interleaved) → Union-Find (amortized hampir konstan per op)
• Ada delete edge → bukan Union-Find (tidak support)

TL;DR: Union-Find = tracking grup terpisah dengan find/union ~O(1). Wajib path compression + union by rank. Foundation Kruskal MST dan banyak masalah connectivity.