Komponen Bersambung Kuat
Kumpulkan nod yang saling boleh dicapai dengan Tarjan.
Komponen Bersambung Kuat ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah Itu SCC
Komponen bersambung kuat ialah kumpulan maksimum nod yang setiap satunya boleh mencapai setiap nod lain dengan mengikuti sisi berarah.
Mengapa Ini Penting
Menggabungkan setiap SCC menjadi satu nod super menukarkan mana-mana graf berarah kepada DAG. Ini memudahkan penaakulan tentang kebergantungan bersama.
Tarjan dalam Satu Laluan
Algoritma Tarjan menemukan setiap SCC dalam satu DFS sahaja. Algoritma ini berjalan dalam O(V + E), iaitu kos yang sama seperti satu penerokaan biasa.
Nombor Penemuan
Berikan setiap nod satu masa penemuan mengikut urutan DFS mula-mula melawatinya. Nombor ini membolehkan anda membandingkan nod yang dilihat lebih awal.
disc = [-1] * n
timer = 0Nilai Paut Rendah
Nilai paut rendah setiap nod ialah ID penemuan paling kecil yang boleh dicapai daripadanya, termasuk melalui sisi belakang. Nilai ini menjadi penambat komponen.
low = [-1] * nTolak ke Dalam Timbunan
Apabila DFS memasuki nod, tetapkan disc dan low, kemudian tolak nod itu ke dalam timbunan nod yang mungkin berkongsi komponennya.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueKemas Kini low daripada Anak
Selepas melakukan rekursi ke anak yang belum dilawati, tarik nilai low anak ke atas: low[u] menjadi nilai minimum antara nilainya sendiri dengan low anak itu.
dfs(v)
low[u] = min(low[u], low[v])Kendalikan Sisi Belakang
Jika jiran sudah dalam timbunan, jiran itu ialah leluhur dalam SCC ini. Gunakan disc-nya untuk mengurangkan low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Kenal Pasti Akar Komponen
Apabila low[u] sama dengan disc[u], nod u ialah akar SCC. Semua nod di atasnya dalam timbunan tergolong dalam komponen yang sama.
Keluarkan Komponen
Di akar, gunakan pop untuk mengeluarkan nod daripada timbunan sehingga u dikeluarkan. Kumpulan yang dikeluarkan itu tepat satu komponen bersambung kuat.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju sebagai Alternatif
Lebih suka dua laluan? Kosaraju menjalankan DFS, membalikkan setiap sisi, kemudian menjalankan DFS sekali lagi mengikut urutan selesai untuk mengasingkan SCC.
Semakan Pantas
Semasa DFS Tarjan, nod u memenuhi low[u] == disc[u]. Apakah maksudnya?
Rumusan: SCC dengan Tarjan
Jejaki disc dan low dalam satu DFS, simpan nod aktif dalam timbunan, dan keluarkan satu komponen setiap kali low sama dengan disc. SCC dalam O(V+E). 🧩
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Komponen Bersambung Kuat” percuma?
Ya — teks penuh “Komponen Bersambung Kuat” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Komponen Bersambung Kuat”?
Kumpulkan nod yang saling boleh dicapai dengan Tarjan. Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Komponen Bersambung Kuat” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Isihan Topologi dengan Algoritma Kahn
- Kesan Kitaran dalam Graf Berarah
- Komponen Bersambung Kuat
- Jambatan dan Titik Artikulasi