Komponen Terhubung Kuat
Mengelompokkan node yang saling dapat dijangkau dengan Tarjan
Komponen Terhubung Kuat adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Pengertian SCC
Komponen terhubung kuat adalah kelompok maksimal simpul yang setiap simpulnya dapat mencapai semua simpul lainnya dengan mengikuti sisi berarah.
Mengapa Ini Penting
Menggabungkan setiap SCC menjadi satu simpul super mengubah graf berarah apa pun menjadi DAG. Hal ini memudahkan analisis dependensi timbal balik.
Tarjan dalam Satu Lintasan
Algoritme Tarjan menemukan setiap SCC dalam satu DFS. Algoritme ini berjalan dalam O(V + E), dengan biaya yang sama seperti satu penelusuran biasa.
Nomor Penemuan
Beri setiap simpul sebuah waktu penemuan sesuai urutan pertama kali DFS mengunjunginya. Id ini memungkinkan Anda membandingkan simpul mana yang ditemukan lebih dahulu.
disc = [-1] * n
timer = 0Nilai Tautan Rendah
low-link setiap simpul adalah id penemuan terkecil yang dapat dicapai dari simpul tersebut, termasuk melalui sisi mundur. Nilai ini menjadi penentu komponen.
low = [-1] * nMasukkan ke Tumpukan
Ketika DFS memasuki sebuah simpul, tetapkan disc dan low-nya, lalu lakukan push ke tumpukan simpul yang mungkin menjadi bagian dari komponennya.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TruePerbarui Low dari Anak
Setelah melakukan rekursi ke anak yang belum dikunjungi, tarik nilai low anak tersebut ke atas: low[u] menjadi nilai minimum antara nilainya sendiri dan low milik anak tersebut.
dfs(v)
low[u] = min(low[u], low[v])Tangani Sisi Mundur
Jika sebuah tetangga sudah berada di tumpukan, tetangga itu adalah leluhur dalam SCC ini. Gunakan disc miliknya untuk menurunkan low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Temukan Akar Komponen
Ketika low[u] sama dengan disc[u], simpul u adalah akar sebuah SCC. Semua simpul di atasnya pada tumpukan termasuk dalam komponen yang sama.
Lakukan Pop pada Komponen
Pada sebuah akar, lakukan pop pada simpul-simpul dari tumpukan sampai u terhapus. Kelompok yang dikeluarkan itu tepat merupakan satu komponen terhubung kuat.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju sebagai Alternatif
Lebih menyukai dua lintasan? Algoritme Kosaraju menjalankan DFS, membalik setiap sisi, lalu menjalankan DFS lagi berdasarkan urutan selesai untuk memisahkan SCC.
Uji Cepat
Selama DFS Tarjan, simpul u memenuhi low[u] == disc[u]. Apa yang dapat Anda simpulkan?
Rangkuman: SCC dengan Tarjan
Lacak disc dan low dalam satu DFS, simpan simpul aktif di tumpukan, lalu lakukan pop pada sebuah komponen setiap kali low sama dengan disc. SCC dalam O(V+E). 🧩
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Komponen Terhubung Kuat” gratis?
Ya — teks lengkap “Komponen Terhubung Kuat” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Komponen Terhubung Kuat”?
Mengelompokkan node yang saling dapat dijangkau dengan Tarjan Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Komponen Terhubung Kuat” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pengurutan Topologis dengan Algoritma Kahn
- Mendeteksi Siklus dalam Graf Berarah
- Komponen Terhubung Kuat
- Jembatan & Titik Artikulasi