Jembatan & Titik Artikulasi
Menemukan sisi dan node yang memutus keterhubungan
Jembatan & Titik Artikulasi adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 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.
Bagian Rapuh dalam Graf
Beberapa bagian graf tak berarah bersifat kritis: jika dihapus, graf akan terpecah. Menemukannya akan mengungkap titik lemah.
Pengertian Jembatan
Jembatan adalah sisi yang penghapusannya menambah jumlah komponen terhubung. Sisi ini merupakan satu-satunya jalur antara dua wilayah.
Pengertian Titik Artikulasi
Titik artikulasi adalah simpul yang jika dihapus akan membuat graf tidak terhubung. Jaringan sangat rentan terhadap satu titik kegagalan seperti ini.
Pohon DFS Lagi
Keduanya berjalan dalam satu DFS dengan melacak waktu penemuan dan nilai low, mirip dengan Tarjan tetapi pada graf tak berarah.
disc = [-1] * n
low = [-1] * nLow Menunjukkan Jangkauan Terjauh
low sebuah simpul adalah id penemuan paling awal yang dapat dicapai dari subpohon DFS-nya, mungkin melalui satu sisi mundur ke atas.
Inisialisasi Saat Masuk
Ketika DFS memasuki sebuah simpul, tetapkan disc dan low ke pewaktu saat ini, lalu lanjutkan ke tetangga-tetangganya.
disc[u] = low[u] = timer
timer += 1Kondisi Jembatan
Setelah melakukan rekursi ke anak v, jika low[v] > disc[u], tidak ada sisi mundur yang melewati u, sehingga sisi u-v adalah jembatan.
if low[v] > disc[u]:
bridges.append((u, v))Kondisi Titik Artikulasi
u yang bukan akar merupakan titik artikulasi jika seorang anak v memenuhi low[v] >= disc[u]: subpohon v tidak dapat melewati u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Kasus Khusus Akar
Akar DFS adalah titik artikulasi hanya jika memiliki dua anak atau lebih dalam pohon DFS, jadi hitung jumlahnya.
if parent[u] == -1 and children > 1:
art.add(u)Lewati Sisi Induk
Saat memperbarui low dari sisi mundur, jangan kembali melalui sisi menuju induk Anda, atau Anda akan salah menilai jembatan.
if v != parent[u]:
low[u] = min(low[u], disc[v])Satu Lintasan, Dua Jawaban
Satu DFS dapat menemukan semua jembatan dan titik artikulasi sekaligus dalam O(V + E). Tidak diperlukan penelusuran tambahan.
Uji Cepat
Setelah melakukan rekursi dari u ke anak v, Anda menemukan low[v] > disc[u]. Apa yang telah Anda temukan?
Rangkuman: Sisi dan Simpul Kritis
Satu DFS dengan disc dan low menemukan semuanya: low[v] > disc[u] menandai jembatan, sedangkan low[v] >= disc[u] menandai titik artikulasi. 🌉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jembatan & Titik Artikulasi” gratis?
Ya — teks lengkap “Jembatan & Titik Artikulasi” 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 “Jembatan & Titik Artikulasi”?
Menemukan sisi dan node yang memutus keterhubungan 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 4 dari 4.
Berapa lama pelajaran “Jembatan & Titik Artikulasi” 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