Bagaimana Anda akan mengimplementasikan algoritma Tarjan untuk komponen terhubung kuat (strongly connected components)?

Pertanyaan dan skenario

Graf memiliki n simpul (vertices) dan m sisi berarah (directed edges). Simpul mungkin tidak memiliki sisi keluar, sisi dapat berulang, dan graf tidak dijamin terhubung. Komponen terhubung kuat (strongly connected component) adalah sebuah himpunan di mana setiap pasangan simpul dapat saling menjangkau. Kembalikan semua komponen dan jelaskan bagaimana mengontraksikannya membentuk graf asiklik berarah (directed acyclic graph / DAG).

Apa yang diuji oleh pewawancara

• Bisakah kandidat mengelola indeks DFS, nilai low, keanggotaan stack, dan ID komponen dengan benar?
• Bisakah mereka membedakan tree edges, back edges, dan sisi ke komponen yang sudah selesai saat memperbarui low?
• Apakah mereka mencakup graf yang terputus, self-loop, sisi paralel, dan risiko kedalaman rekursi?
• Bisakah mereka menyatakan waktu O(n+m) dan ruang bantu O(n) serta menguji invarian tersebut?

Pertanyaan klarifikasi untuk ditanyakan terlebih dahulu

Konfirmasikan apakah ID simpul berurutan (contiguous), apakah sisi paralel diperbolehkan, apakah anggota komponen perlu diurutkan, dan apakah runtime membatasi kedalaman rekursi. Klarifikasi ukuran graf, kebutuhan pembaruan inkremental, dan apakah hanya diperlukan kueri komponen yang sama. Untuk graf yang sangat dalam, sampaikan pertukaran (trade-off) antara rekursi dan stack eksplisit.

Kerangka jawaban 30 detik

Jalankan satu DFS dan tetapkan setiap simpul sebuah indeks yang meningkat dan indeks terkecil yang dapat dijangkau oleh back edge, yang disebut low. Lakukan push dan tandai setiap simpul, lalu periksa tetangganya: lakukan rekursi pada tetangga yang belum dikunjungi dan gunakan low miliknya; untuk tetangga yang masih ada di dalam stack, gunakan indeksnya. Ketika low sama dengan indeks simpul itu sendiri, simpul tersebut adalah root komponen; lakukan pop hingga simpul tersebut. Setiap simpul dan sisi menerima operasi konstan, sehingga kompleksitasnya adalah O(n+m).

Pembahasan mendalam langkah demi langkah

1. Inisialisasi state. Simpan indeks, low, flag keanggotaan stack, dan ID komponen untuk setiap simpul. Mulai DFS dari setiap simpul yang belum dikunjungi untuk mencakup input yang terputus.
2. Proses tetangga yang belum dikunjungi. Lakukan rekursi, lalu terapkan low[u] = min(low[u], low[v]). Ini mencatat jalur dari subtree DFS kembali ke simpul stack sebelumnya.
3. Proses tetangga di dalam stack. Jika tetangga masih ada di dalam stack, perbarui low[u] dengan indeks tetangga tersebut. Simpul yang sudah di-pop ke dalam komponen lain tidak dapat berpartisipasi dalam backtrack ini.
4. Temukan root dan lakukan pop. Ketika low[u] == index[u], u adalah root. Lakukan pop dan bersihkan flag keanggotaan hingga u di-pop; simpul-simpul tersebut membentuk satu komponen terhubung kuat.
5. Tangani kasus batas. Self-loop tetap menghasilkan komponen tunggal (singleton); sisi paralel mengulangi pembaruan minimum yang sama; simpul terisolasi menjadi singleton ketika di-push.
6. Validasi dan kondensasikan. Periksa bahwa setiap simpul menjadi anggota tepat satu komponen dan bahwa sisi antar-komponen membentuk DAG. Bandingkan graf kecil acak dengan transitive closure atau Kosaraju, lalu uji kompleksitas dan kedalaman stack pada graf besar.

Contoh jawaban berkualitas tinggi

Saya akan mengelola empat array: index yang meningkat, nilai back-link low, flag keanggotaan stack, dan ID komponen. Saat memasuki DFS, tetapkan indeks dan lakukan push pada simpul. Untuk tetangga yang belum dikunjungi, lakukan rekursi dan teruskan nilai low-nya; untuk tetangga yang masih ada di dalam stack, teruskan hanya indeks tetangga tersebut. Komponen yang telah selesai tidak pernah berpartisipasi dalam pembaruan.

Ketika low[u] == index[u], u adalah root, jadi lakukan pop hingga u dan bersihkan flag. Mulai DFS dari setiap simpul yang belum dikunjungi, sehingga konektivitas tidak diasumsikan. Setiap simpul di-push dan di-pop satu kali dan setiap sisi diperiksa satu kali, menghasilkan waktu O(n+m) dan ruang bantu O(n). Pengujian mencakup self-loop, sisi paralel, simpul terisolasi, rantai panjang, banyak siklus, dan graf yang terputus, ditambah pemartisian komponen dan DAG kondensasi.

Kesalahan umum

• Memperbarui dari nilai low setiap tetangga yang dikunjungi dan secara tidak sengaja melakukan backtrack melintasi komponen yang telah selesai.
• Lupa membersihkan keanggotaan stack setelah melakukan pop pada suatu komponen, sehingga sisi berikutnya memperlakukan simpul lama sebagai leluhur saat ini.
• Memulai DFS hanya dari satu simpul dan melewatkan komponen pada input yang terputus.
• Menafsirkan low yang sama dengan indeks saat ini sebagai "tidak ada sisi" alih-alih "simpul ini adalah root komponen."
• Melebihi batas stack bahasa tanpa mendiskusikan stack eksplisit, chunking, atau konfigurasi runtime.

Pertanyaan lanjutan dan jawabannya

Mengapa simpul yang sudah di-pop tidak dapat memperbarui low?

Simpul tersebut sudah menjadi bagian dari komponen yang selesai dan bukan lagi leluhur backtrack pada jalur DFS saat ini. Menggunakan nilai low miliknya akan melintasi batas komponen dan merusak maksimalitas.

Bagaimana Anda membuktikan setiap komponen di-pop tepat satu kali?

Setiap simpul di-push satu kali, dan hanya root yang dapat memicu operasi pop. Setelah di-pop, flag stack-nya dibersihkan dan DFS tidak pernah melakukan push lagi padanya, sehingga setiap simpul berada tepat di satu komponen.

Bagaimana Anda memilih antara Tarjan versus Kosaraju?

Tarjan menggunakan satu kali DFS dan tanpa graf transposisi, yang dapat mengurangi traversal dan penyimpanan. Kosaraju menggunakan dua lintasan DFS dan memisahkan tahap-tahapnya dengan jelas. Keduanya adalah O(n+m); pilih berdasarkan batas stack, keterbacaan kode, dan representasi graf yang ada.