Wawancara Koding: Bagaimana Cara Mengimplementasikan Union-Find dan Melacak Komponen Terhubung?

Permintaan dan Cakupan Masalah

Terdapat n simpul yang diberi label dari 0 hingga n - 1. Pada awalnya, setiap simpul merupakan komponen terhubungnya sendiri. Implementasikan UnionFind dengan operasi-operasi berikut:

• union(a, b) menggabungkan komponen yang memuat a dan b. Fungsi ini mengembalikan True hanya jika dua

komponen yang sebelumnya berbeda benar-benar digabungkan.

• connected(a, b) melaporkan apakah kedua simpul saat ini berada dalam komponen yang sama.
• count() mengembalikan jumlah komponen terhubung saat ini.

Versi ini mengizinkan n = 0, tetapi setiap argumen operasi harus berupa label yang valid atau memunculkan IndexError. Masalah dasar ini hanya menambahkan koneksi; masalah ini tidak menghapus tepi (edge), dan pemanggilan fungsi berasal dari satu thread. Sebagai contoh, setelah dimulai dengan n = 6 dan menggabungkan (0, 1), (1, 2), serta (3, 4), tiga komponen yang terbentuk adalah {0, 1, 2}, {3, 4}, dan {5}. Menggabungkan (2, 4) menyisakan dua komponen. Pemanggilan union(0, 3) berikutnya harus mengembalikan False tanpa mengurangi jumlah komponen lagi.

Ini adalah masalah wawancara struktur data rekayasa perangkat lunak umum. Kasus penggunaan utamanya adalah aliran koneksi inkremental yang diselingi dengan banyak kueri konektivitas dan penghitungan komponen. Jika semua tepi diberikan sekaligus dan pemanggil hanya memerlukan satu kali penghitungan komponen, DFS atau BFS sering kali lebih langsung; mengenali perbedaan tersebut adalah bagian dari jawaban yang kuat.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah pemilihan state. Union-Find tidak menyimpan keseluruhan graf. Struktur ini merepresentasikan setiap himpunan sebagai pohon penunjuk-induk (parent-pointer tree) yang akarnya merupakan perwakilan himpunan dan menunjuk ke dirinya sendiri. Konsekuensinya, connected(a, b) dapat membandingkan dua akar alih-alih menelusuri setiap tepi yang tersimpan.

Sinyal kedua adalah apakah operasi union hanya menghubungkan akar. Menulis parent[a] = b secara langsung dapat memindahkan sebuah simpul internal ke bawah simpul lain dan merusak representasi komponen aslinya. Urutan yang benar adalah mencari root_a dan root_b, memastikan bahwa keduanya berbeda, lalu menghubungkan akar pohon yang lebih kecil ke akar pohon yang lebih besar. size hanya bermakna pada akar dan mengontrol pertumbuhan tinggi pohon.

Sinyal ketiga adalah penjelasan mengenai kompresi jalur (path compression), bukan sekadar templat yang dihafal. Implementasi ini menggunakan path halving: saat find berjalan ke atas, ia mengubah induk dari simpul saat ini menjadi kakeknya (grandparent). Induk baru tersebut masih berada di pohon yang sama, sehingga konektivitas tidak berubah sementara jalur di masa mendatang menjadi lebih pendek. Bentuk iteratif juga menghindari kegagalan batas kedalaman rekursi (recursion depth limit) pada jalur yang panjang.

Terakhir, pewawancara memeriksa invarian hitungan komponen, terminologi kompleksitas, dan verifikasi. components dimulai dari n dan hanya berkurang setelah dua akar yang berbeda digabungkan. Union duplikat dan self-union tidak boleh mengubahnya. Dengan menggabungkan union by size dan path compression, operasi-operasi tersebut membutuhkan waktu teramortisasi O(α(n)) sepanjang suatu rangkaian operasi—bukan kasus terburuk mutlak (strict worst-case) O(1) untuk setiap pemanggilan.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah koneksi hanya ditambahkan, atau bisakah juga dihapus? Union-Find standar menangani penambahan.

Setelah penghapusan tepi arbitrer, hutan induk (parent forest) tidak dapat mengetahui apakah ada tepi lain yang masih menghubungkan kedua titik ujung; hal itu memerlukan metode offline atau struktur konektivitas dinamis yang lebih canggih.

• Apakah kueri diselingi secara online, atau semua tepi diberikan di awal? Kueri union dan

konektivitas yang diselingi lebih cocok menggunakan Union-Find. Untuk satu kali penghitungan komponen pada graf statis, DFS/BFS dengan adjacency list lebih transparan dan tetap mempertahankan tepi yang sebenarnya.

• Apa yang harus dikembalikan oleh union? Di sini fungsi tersebut melaporkan apakah penggabungan terjadi. Nilai boolean tersebut mendukung

deteksi siklus secara langsung dan memastikan bahwa jumlah komponen berubah tepat satu kali.

• Bagaimana perilaku untuk simpul yang tidak valid? Versi ini memunculkan IndexError. Solusi kompetisi pemrograman dapat mengabaikan

validasi di bawah kontrak input yang dijamin valid, tetapi indeks negatif pada Python tidak boleh secara diam-diam merujuk ke akhir larik dalam implementasi publik.

• Haruskah API melaporkan ukuran komponen atau mengenumerasi anggota? size pada akar dapat menjawab ukuran dalam waktu

teramortisasi yang hampir konstan. Mengenumerasi anggota tetap membutuhkan biaya setidaknya sebesar ukuran output, dan struktur dasar ini tidak memelihara daftar anggota.

• Apakah pemanggilan fungsi dapat dilakukan secara konkuren? Implementasi dasar memutasi parent di dalam find, sehingga bahkan

kueri konektivitas bukanlah operasi read-only atau thread-safe. Konkurensi memerlukan kontrak penguncian (locking contract) atau algoritma Union-Find konkuren khusus.

Kerangka Jawaban 30 Detik

"Saya akan memelihara dua larik dengan panjang n: parent[x] menunjuk ke induk, dan size[root] menyimpan ukuran pohon milik akar. Awalnya setiap simpul adalah induknya sendiri dan jumlah komponen adalah n. find berjalan ke akar dan melakukan path halving dengan mengarahkan setiap simpul yang dikunjungi ke kakeknya. union mencari kedua akar; jika sama, fungsi mengembalikan False. Jika tidak, fungsi akan menghubungkan akar pohon yang lebih kecil ke akar pohon yang lebih besar, menjumlahkan ukurannya, mengurangi jumlah komponen, dan mengembalikan True. Menghubungkan dua akar tidak dapat menciptakan siklus, dan path halving hanya mengubah penunjuk di dalam satu himpunan, sehingga konektivitas tetap benar. Inisialisasi membutuhkan O(n); operasi selanjutnya berdurasi teramortisasi O(α(n)) dengan ruang O(n)."

Pembahasan Mendalam Langkah demi Langkah

Representasi langsung menetapkan label komponen ke setiap simpul. connected adalah perbandingan label, tetapi menggabungkan dua komponen memerlukan pemindaian seluruh larik dan mengganti setiap label lama, sehingga satu kali union memakan biaya O(n). Pendekatan naif lainnya menggunakan pohon penunjuk-induk tetapi menghubungkan akar tanpa mengontrol ukurannya. Urutan union yang dirancang secara buruk (adversarial) dapat menciptakan rantai panjang dan menurunkan performa find.

Desain yang direkomendasikan memelihara tiga bagian state:

1. parent[x] adalah induk dari x, dan setiap akar pohon memenuhi parent[root] == root.
2. size[root] adalah jumlah simpul dari komponen milik akar tersebut; nilai usang pada non-akar tidak pernah dibaca.
3. components sama dengan jumlah akar di dalam hutan induk.

Implementasinya adalah sebagai berikut. _validate berukuran pendek dan hanya digunakan oleh kelas ini, sehingga tetap diletakkan di samping lokasi pemanggilannya alih-alih menjadi modul utilitas terpisah.

class UnionFind:
    def __init__(self, n: int) -> None:
        if n < 0:
            raise ValueError("n must be non-negative")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def _validate(self, x: int) -> None:
        if x < 0 or x >= len(self.parent):
            raise IndexError("node out of range")

    def find(self, x: int) -> int:
        self._validate(x)
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def count(self) -> int:
        return self.components

Kebenaran algoritma dibuktikan dalam tiga langkah. Awalnya, setiap simpul adalah satu-satunya akar dari pohon satu simpul, sehingga hutan memiliki n pohon dan ketiga invarian terpenuhi. Path halving mengubah induk dari x menjadi induk dari induk aslinya (kakek). Kakek tersebut tetap berada pada jalur yang sama menuju akar asli, sehingga operasi ini tidak dapat melintasi komponen lain atau mengubah akar yang dikembalikan oleh find(x).

Operasi union hanya memodifikasi dua akar. Akar yang sama berarti simpul-simpul tersebut sudah terhubung, sehingga tidak ada state yang berubah. Untuk akar yang berbeda, mengarahkan root_b ke root_a menggabungkan dua pohon menjadi satu dan tidak dapat menciptakan siklus karena akar-akar tersebut berasal dari pohon yang terpisah. Ukuran akar yang baru adalah jumlah dari ukuran pohon-pohon lama, dan jumlah akar berkurang tepat satu. Secara induksi, dua simpul terhubung jika dan hanya jika find mengembalikan akar yang sama, dan count() selalu cocok dengan jumlah komponen yang sebenarnya.

Union by size menjamin bahwa setiap kali kedalaman suatu simpul bertambah karena seluruh pohonnya digabungkan, ukuran komponen barunya setidaknya menjadi dua kali lipat. Bahkan tanpa kompresi jalur, tinggi pohon paling banyak adalah O(log n). Dikombinasikan dengan path halving, serangkaian m operasi find dan union setelah inisialisasi memiliki batas teramortisasi O(m α(n)). Fungsi invers Ackermann α tumbuh sangat lambat. "Waktu teramortisasi yang hampir konstan" adalah istilah ringkas yang akurat dalam wawancara; "kasus terburuk mutlak O(1)" adalah keliru. Kedua larik menggunakan ruang O(n), dan find iteratif menggunakan ruang tumpukan (stack space) pembantu sebesar O(1).

State dapat ditelusuri dengan urutan operasi berikut:

n = 6                         count = 6
union(0, 1) -> True           count = 5
union(1, 2) -> True           count = 4
union(3, 4) -> True           count = 3
connected(0, 2) -> True
connected(0, 4) -> False
union(2, 4) -> True           count = 2
union(0, 3) -> False          count = 2

Verifikasi membutuhkan lebih dari satu contoh. Cakup kasus n = 0 tanpa kueri, self-union pada n = 1, union duplikat, dua komponen terpisah yang dihubungkan oleh sebuah jembatan (bridge), simpul terisolasi, operasi union yang diberikan dalam urutan terbalik, serta label yang tidak valid -1 dan n. Untuk graf kecil acak, pelihara sebuah adjacency list sebagai pembanding (oracle). Setelah setiap penyisipan tepi, hitung ulang konektivitas dan jumlah komponen dengan BFS, lalu bandingkan langkah demi langkah dengan Union-Find. Pengujian diferensial ini dapat menangkap bug halus pada penghitungan komponen dan penentuan akar.

Jika semua m tepi diketahui di awal dan pemanggil meminta satu kali penghitungan komponen, DFS/BFS dengan adjacency list menggunakan waktu dan ruang sebesar O(n + m) serta menyatakan tujuannya dengan jelas. Union-Find sangat berguna saat tepi datang secara inkremental dan kueri diselingi dengan operasi union, atau ketika algoritma Kruskal perlu menguji apakah tepi tak berarah akan menciptakan siklus. Model operasi—bukan sekadar keberadaan sebuah graf—yang menentukan pilihan struktur data.

Contoh Jawaban Berkualitas Tinggi

"Pertama, saya akan mengonfirmasi bahwa relasi hanya ditambahkan, kueri diselingi dengan penambahan, dan union harus melaporkan apakah penggabungan terjadi. Model operasi tersebut sangat cocok dengan Union-Find. Jika ini adalah satu kali penghitungan komponen pada graf statis, saya akan menggunakan DFS.

State saya adalah parent, size pada akar, dan jumlah akar saat ini dalam components. Setiap simpul pada awalnya menunjuk ke dirinya sendiri. find berjalan secara iteratif menuju akar dan mengarahkan setiap simpul yang dikunjungi ke kakeknya, memperpendek jalur tanpa rekursi. union mendapatkan kedua akar. Akar yang sama mengembalikan False dan tidak mengubah jumlah komponen. Jika berbeda, akar pohon yang lebih kecil menunjuk ke akar pohon yang lebih besar, ukurannya dijumlahkan, dan jumlah komponen dikurangi satu.

Representasi ini tetap berupa hutan. Path halving hanya mengarahkan simpul ke leluhur di pohon yang sama, dan union menghubungkan akar dari dua pohon yang berbeda, sehingga tidak ada operasi yang menciptakan siklus induk. Setiap union yang berhasil mengubah tepat dua pohon menjadi satu, yang juga membuktikan invarian hitungan komponen.

Mengonstruksi larik membutuhkan biaya O(n). Dengan union by size dan path halving, operasi find, connectivity, dan union membutuhkan waktu teramortisasi O(α(n)), dengan ruang O(n). Pengujian saya menekankan pada self-union dan union duplikat yang tidak mengubah hitungan, menjembatani dua komponen besar, simpul terisolasi, struktur kosong, dan label negatif yang tidak valid. Saya juga akan melakukan pengujian diferensial pada kasus-kasus kecil acak terhadap BFS."

Kesalahan Umum

• Menetapkan parent[a] = b secara langsung → a mungkin bukan akar, sehingga pohon asli dapat terpecah atau

berubah menjadi rantai yang tidak terkendali → Cari kedua akar dan hubungkan hanya pada akar.

• Selalu menghubungkan pohon kedua ke pohon pertama → urutan yang buruk dapat menciptakan jalur yang panjang → **Gunakan

size atau rank pada akar untuk memilih arah penggabungan.**

• Hanya mengembalikan parent[x] dari find → induk belum tentu merupakan akar, sehingga konektivitas

tidak langsung salah diklasifikasikan → Ikuti penunjuk sampai menemukan akar yang menunjuk ke dirinya sendiri.

• Mengurangi components setelah setiap pemanggilan union → union duplikat dan self-union akan membuat

hitungan menjadi lebih kecil dari yang sebenarnya → Perbarui hitungan hanya jika akarnya berbeda.

• Memperbarui ukuran akar lama setelah menukar akar → metadata menjadi tidak sesuai dengan pohon sebenarnya →

Pilih akar induk akhir terlebih dahulu, lalu hubungkan dan tambahkan ukuran secara konsisten.

• Mengklaim kasus terburuk O(1) per operasi → jaminan tersebut teramortisasi sepanjang suatu rangkaian operasi dan

mencakup fungsi invers Ackermann → Laporkan sebagai teramortisasi O(α(n)).

• Mengabaikan indeks negatif pada Python → find(-1) mengakses simpul terakhir alih-alih memunculkan error →

Validasi kedua batas indeks dalam implementasi publik.

• Menggunakan Union-Find dasar untuk penghapusan tepi arbitrer → penunjuk induk tidak mempertahankan jalur

alternatif setelah penghapusan → Gunakan pemrosesan penghapusan offline, rollback Union-Find, atau struktur konektivitas dinamis.

• Memperlakukan connected sebagai read-only → path halving menulis ke parent, menyebabkan race condition di bawah

pemanggilan konkuren → Tentukan aturan sinkronisasi sebelum memilih global lock, partisi, atau algoritma konkuren.

Pertanyaan Lanjutan dan Cara Menanganinya

Pertanyaan Lanjutan 1: Bagaimana Union-Find dapat mendeteksi siklus dalam graf tak berarah?

Proses tepi (u, v) satu per satu. Jika union(u, v) mengembalikan False, titik-titik ujung tersebut sudah terhubung sebelum tepi baru ditambahkan, sehingga tepi tersebut menutup sebuah siklus. Hasil True hanya menggabungkan dua komponen yang sebelumnya terpisah. Aturan ini berlaku langsung untuk graf tak berarah. Deteksi siklus pada graf berarah memerlukan metode lain seperti three-color DFS atau pemilahan topologis (topological sorting).

Pertanyaan Lanjutan 2: Bagaimana jika pemanggil perlu membatalkan (undo) operasi union terakhir?

Gunakan rollback Union-Find. Pertahankan union by size dan masukkan nilai induk lama, ukuran akar, serta jumlah komponen dari setiap perubahan nyata ke dalam history stack sebelum memodifikasinya. Operasi undo akan mengembalikan nilai-nilai tersebut. Path compression biasanya dihilangkan karena satu kali find memutasi banyak entri, sehingga memperbesar log rollback dan memperumit batasan operasi. Union by size saja membatasi tinggi pohon hingga O(log n) dan bekerja sangat baik dengan metode divide-and-conquer pada linimasa operasi offline.

Pertanyaan Lanjutan 3: Bagaimana jika relasi dapat dihapus secara arbitrer?

Union-Find standar tidak dapat menangani penghapusan online yang arbitrer. Jika seluruh rangkaian operasi diketahui di awal, tempatkan interval aktif setiap tepi ke dalam segment tree sepanjang waktu dan telusuri dengan rollback Union-Find; penghapusan yang hanya terjadi di akhir juga dapat diproses secara terbalik sebagai penambahan. Operasi penyisipan, penghapusan, dan kueri yang benar-benar online dan sering memerlukan struktur konektivitas dinamis penuh (fully dynamic connectivity) yang lebih canggih. Oleh karena itu, memastikan apakah operasi bersifat offline adalah klarifikasi penting penentu masalah.

Pertanyaan Lanjutan 4: Bagaimana cara mengembalikan ukuran komponen atau seluruh anggotanya?

Ukuran sudah tersimpan di akar, sehingga size_of(x) = size[find(x)] mempertahankan batas waktu teramortisasi yang sama. Mendapatkan daftar anggota tidak dapat dilakukan hanya dari ukuran akar. Memindai semua simpul dan membandingkan akar memakan biaya O(n α(n)); memelihara himpunan anggota menambah biaya penggabungan dan memori. Pemindaian biasanya lebih sederhana jika hanya untuk ekspor sesekali. Enumerasi yang sering dapat menjadi alasan untuk menggunakan representasi data yang berbeda.

Pertanyaan Lanjutan 5: Bagaimana Anda menangani pemanggilan dari banyak thread?

Perubahan terkecil yang benar adalah menggunakan satu mutex di sekitar find, union, dan connected, karena path halving menulis ke larik parent. Ini mudah dibuktikan kebenarannya tetapi menserialisasikan semua operasi. Hanya pertentangan (contention) yang terukur yang membenarkan desain konkuren berdasarkan atomic compare-and-swap, deterministic linking, atau partisi. Desain semacam itu harus membuktikan kembali penunjuk induk yang asiklik serta pembaruan ukuran dan jumlah komponen secara atomik; mengganti larik dengan variabel atomik saja tidak cukup.