Bagaimana cara kerjanya?

Union-find menyimpan array parent. Setiap vertex dimulai sebagai root-nya sendiri. Dua operasi mengendalikan semuanya:

• find(x): ikuti tautan parent sampai kamu mencapai root (vertex yang menjadi parent bagi dirinya sendiri). Dua vertex terhubung jika keduanya memiliki root yang sama.
• union(a, b): arahkan satu root ke root lainnya, lalu gabungkan kedua set.

Algoritma Kruskal:

1. Proses edge dari bobot terkecil ke terbesar.
2. Untuk setiap edge, cari root dari kedua ujungnya dengan find. Jika keduanya berbeda, edge tersebut menghubungkan dua bagian yang terpisah: gabungkan keduanya dengan union dan tambahkan bobotnya ke total.
3. Jika root-nya sama, edge tersebut akan membentuk siklus, jadi lewati.

Setelah semua edge diproses, edge yang dipilih membentuk MST (untuk graph yang terhubung, tepat n - 1 edge).