Bagaimanakah anda akan melaksanakan algoritma Tarjan untuk komponen berkaitan kuat (strongly connected components)?

Soalan dan senario

Graf mempunyai n bucu dan m tepi berarah. Bucu mungkin tidak mempunyai tepi keluar, tepi boleh berulang, dan graf tidak dijamin bersambung. Komponen berkaitan kuat ialah satu set di mana setiap pasangan bucu boleh mencapai antara satu sama lain. Kembalikan semua komponen dan terangkan bagaimana mengecutkannya membentuk graf asiklik berarah (DAG).

Perkara yang diuji oleh penemu duga

• Bolehkah calon mengekalkan indeks DFS, nilai low, keahlian tindanan, dan ID komponen dengan betul?
• Bolehkah mereka membezakan tepi pokok (tree edges), tepi belakang (back edges), dan tepi ke komponen yang telah selesai semasa mengemas kini low?
• Adakah mereka merangkumi graf terputus, gelung diri, tepi selari, dan risiko kedalaman rekursi?
• Bolehkah mereka menyatakan masa O(n+m) dan ruang bantuan O(n) serta menguji batas tak berubah tersebut?

Soalan penjelasan untuk ditanya terlebih dahulu

Sahkan sama ada ID bucu adalah berturutan, sama ada tepi selari dibenarkan, sama ada ahli komponen perlu diisih, dan sama ada masa jalanan (runtime) mengehadkan kedalaman rekursi. Jelaskan saiz graf, keperluan kemas kini bertambah (incremental), dan sama ada hanya pertanyaan komponen yang sama diperlukan. Untuk graf yang sangat dalam, nyatakan pertukaran antara rekursi dan tindanan eksplisit.

Rangka kerja jawapan 30 saat

Jalankan satu DFS dan tetapkan setiap bucu dengan indeks yang meningkat dan indeks terkecil yang boleh dicapai oleh tepi belakang, yang dipanggil low. Tolak (push) dan tandakan setiap bucu, kemudian periksa jiran: lakukan rekursi pada jiran yang belum dilawati dan gunakan low miliknya; untuk jiran yang masih berada di dalam tindanan, gunakan indeksnya. Apabila low sama dengan indeks bucu itu sendiri, ia adalah punca komponen; lakukan pop sehingga bucu tersebut. Setiap bucu dan tepi menerima kerja malar, jadi kekompleksannya ialah O(n+m).

Panduan terperinci langkah demi langkah

1. Mulakan keadaan (state). Simpan indeks, low, bendera keahlian tindanan, dan ID komponen untuk setiap bucu. Mulakan DFS dari setiap bucu yang belum dilawati untuk merangkumi input yang terputus.
2. Proses jiran yang belum dilawati. Lakukan rekursi, kemudian gunakan low[u] = min(low[u], low[v]). Ini merekodkan laluan dari subpokok DFS kembali ke bucu tindanan yang lebih awal.
3. Proses jiran tindanan. Jika jiran masih berada di dalam tindanan, kemas kini low[u] dengan indeks jiran tersebut. Bucu yang telah dikeluarkan (popped) ke dalam komponen lain tidak boleh mengambil bahagian dalam undur balik (backtrack) ini.
4. Cari punca dan lakukan pop. Apabila low[u] == index[u], u ialah puncanya. Lakukan pop dan kosongkan bendera keahlian sehingga u dikeluarkan; bucu-bucu tersebut membentuk satu komponen berkaitan kuat.
5. Kendalikan sempadan. Gelung diri masih menghasilkan komponen tunggal; tepi selari mengulangi kemas kini minimum yang sama; bucu terpencil menjadi komponen tunggal apabila ia ditolak (pushed).
6. Sahkan dan padatkan. Semak bahawa setiap bucu tergolong dalam tepat satu komponen dan tepi antara komponen membentuk DAG. Bandingkan graf kecil rawak dengan penutupan transitif atau Kosaraju, kemudian uji kekompleksan dan kedalaman tindanan pada graf yang besar.

Contoh jawapan berkualiti tinggi

Saya akan mengekalkan empat tatasusunan: index yang meningkat, nilai pautan belakang low, bendera keahlian tindanan, dan ID komponen. Semasa kemasukan DFS, tetapkan indeks dan tolak bucu tersebut. Untuk jiran yang belum dilawati, lakukan rekursi dan sebarkan nilai low miliknya; untuk jiran yang masih berada di dalam tindanan, sebarkan hanya indeks jiran tersebut. Komponen yang telah selesai tidak pernah mengambil bahagian dalam kemas kini.

Apabila low[u] == index[u], u ialah punca, jadi lakukan pop sehingga u dan kosongkan bendera. Mulakan DFS dari setiap bucu yang belum dilawati, supaya ketersambungan tidak diandaikan. Setiap bucu ditolak dan dikeluarkan sekali dan setiap tepi diperiksa sekali, memberikan masa O(n+m) dan ruang bantuan O(n). Ujian merangkumi gelung diri, tepi selari, bucu terpencil, rantai panjang, pelbagai kitaran, dan graf terputus, serta pemetakan komponen dan DAG pemeluwapan.

Kesilapan biasa

• Mengemas kini daripada nilai low setiap jiran yang dilawati dan secara tidak sengaja berundur balik merentasi komponen yang telah selesai.
• Terlupa mengosongkan keahlian tindanan selepas mengeluarkan komponen, menyebabkan tepi terkemudian menganggap bucu lama sebagai leluhur semasa.
• Memulakan DFS daripada satu bucu sahaja dan terlepas komponen dalam input yang terputus.
• Mentafsirkan low sama dengan indeks semasa sebagai "tiada tepi" dan bukannya "bucu ini ialah punca komponen."
• Melebihi had tindanan bahasa tanpa membincangkan tindanan eksplisit, pemetakan (chunking), atau konfigurasi masa jalanan.

Soalan susulan dan jawapan

Mengapakah bucu yang telah dikeluarkan (popped) tidak boleh mengemas kini low?

Ia telah pun tergolong dalam komponen yang selesai dan bukan lagi leluhur undur balik pada laluan DFS semasa. Menggunakan nilai low miliknya akan merentasi sempadan komponen dan memusnahkan kemaksimuman.

Bagaimanakah anda membuktikan setiap komponen dikeluarkan tepat sekali?

Setiap bucu ditolak sekali, dan hanya punca yang boleh mencetuskan pengeluaran (popping). Selepas dikeluarkan, bendera tindanannya dikosongkan dan DFS tidak akan menolaknya lagi, jadi setiap bucu tergolong dalam tepat satu komponen.

Bagaimanakah anda memilih antara Tarjan berbanding Kosaraju?

Tarjan menggunakan satu DFS dan tiada graf transposisi, yang boleh mengurangkan traversal dan storan. Kosaraju menggunakan dua laluan DFS dan memisahkan peringkat-peringkatnya dengan jelas. Kedua-duanya adalah O(n+m); pilih berdasarkan had tindanan, kebolehbacaan, dan perwakilan graf sedia ada.