Temuduga Pengekodan: Cari Semua Critical Connection dalam Rangkaian

Prom dan Konteks Berkenaan

Anda diberikan n nod berlabel 0 hingga n - 1 dan satu tatasusunan connections, di mana setiap pasangan [u, v] ialah sisi tidak berarah. Graf ini bersambung dan ringkas: ia tidak mempunyai gelung sendiri (self-loop) atau sisi berulang. Kembalikan setiap critical connection, iaitu setiap sisi yang penyingkirannya memutuskan graf. Jawapan boleh dalam sebarang susunan, dan mana-mana susunan titik akhir boleh diterima.

Andaikan 2 <= n <= 100000 dan n - 1 <= connections.length <= 100000. Sebagai contoh:

n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
output = [[1, 3]]

Tiga sisi pertama membentuk satu kitaran, jadi penyingkiran mana-mana satu daripadanya meninggalkan laluan alternatif. Nod 3 hanya mempunyai sisi [1, 3]; penyingkirannya memisahkan nod 3. Dalam istilah graf, critical connection ialah satu bridge.

Ini ialah soalan pengekodan tentang invarian graf. Ia berbeza daripada artikel Union-Find yang sedia ada, yang mengekalkan komponen bersambung semasa sisi ditambah; ia berbeza daripada pengisihan topologi, yang menyusun graf tak berkitar berarah; dan ia berbeza daripada Dijkstra, yang mengoptimumkan panjang laluan berwajaran. Di sini output bergantung pada bagaimana keterhubungan berubah selepas penyingkiran setiap sisi tidak berarah.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon menolak pendekatan carian berulang yang ketara pada skala yang dinyatakan. Menyingkirkan satu sisi dan menjalankan BFS atau DFS menjawab satu pertanyaan dengan betul, tetapi mengulangi perkara itu untuk semua m sisi memerlukan masa O(m(n + m)). Pada 100,000 sisi, traversal linear bagi setiap sisi adalah tidak berdaya maju.

Isyarat kedua ialah invarian low-link yang tepat. Masa penemuan DFS tin[u] merekodkan masa u pertama kali dilawati. low[u] ialah masa penemuan terawal yang boleh dicapai daripada subpokok DFS u dengan menuruni sisi pokok (tree edge) dan kemudian menggunakan paling banyak satu sisi bukan pokok (non-tree edge). Untuk satu sisi pokok DFS u -> v, sisi tersebut ialah bridge tepat apabila low[v] > tin[u].

Isyarat ketiga ialah disiplin pelaksanaan. Pada jiran yang telah dilawati, kemas kini dengan tin[neighbor], bukan low[neighbor]. Langkau sisi tepat yang digunakan untuk memasuki nod, bukan setiap sisi yang titik akhir satu laginya sama dengan induk (parent). ID sisi menjadikan perbezaan itu eksplisit dan memastikan kod kekal betul jika soalan susulan membenarkan sisi selari.

Isyarat keempat ialah kesedaran bahasa peringkat pengeluaran. DFS rekursif adalah padat, tetapi rantaian 100,000 nod boleh melebihi had tindanan panggilan (call-stack) runtime JavaScript. DFS lelaran mesti mensimulasikan kedua-dua fasa kemasukan dan fasa kembali-daripada-anak supaya ia boleh menyebarkan nilai low hanya selepas anak selesai diproses.

Soalan untuk Dijelaskan Sebelum Menjawab

• Adakah graf ini berarah? Tidak. Bridge dalam graf berarah memerlukan definisi dan

algoritma yang berbeza.

• Adakah graf dijamin bersambung? Ya untuk prom asas. Mengulangi setiap

nod yang belum dilawati tidak memerlukan kos asimptotik tambahan dan menjadikan pelaksanaan berfungsi untuk soalan susulan graf tidak bersambung juga.

• Adakah sisi berulang dibenarkan? Tidak dalam prom asas. Pelaksanaan ini masih memberikan ID kepada setiap

sisi, jadi dua sisi selari akan memberikan laluan alternatif dengan betul dan bukannya kedua-duanya dilaporkan sebagai bridge.

• Bolehkah hasilnya menggunakan mana-mana susunan titik akhir? Ya. Jika penghakiman automatik memerlukan output kanonikal, normalkan

setiap sisi kepada [min, max] dan susun hanya selepas mencari bridge.

• Adakah graf ini statik? Ya. Mengekalkan bridge semasa sisi disisipkan atau dipadamkan ialah masalah keterhubungan

dinamik; menjalankan semula algoritma linear ini selepas setiap kemas kini mungkin terlalu mahal.

• Bolehkah saya menggunakan rekursi? Hanya jika persekitaran menjamin kedalaman tindanan yang mencukupi. Dengan n sehingga

100,000 dalam JavaScript atau TypeScript, tindanan eksplisit ialah kontrak yang lebih selamat.

Rangka Jawapan 30 Saat

“Saya akan menjalankan DFS sekali dan menetapkan masa penemuan tin untuk setiap nod. Bagi setiap nod, low merekodkan masa penemuan terawal yang boleh dicapai daripada subpokok DFS miliknya tanpa kembali melalui sisi pokok tepat yang memasukinya. Selepas anak v selesai, jika low[v] > tin[u], subpokok di bawah v tidak mempunyai laluan ke u atau leluhur, jadi [u, v] ialah satu bridge. Jika tidak, satu sisi belakang (back edge) menyediakan laluan alternatif. Saya akan menggunakan ID sisi dan tindanan DFS eksplisit untuk mengendalikan soalan susulan sisi selari serta mengelakkan limpahan tindanan panggilan (call-stack overflow). Setiap entri kejiranan diproses sekali, jadi masa ialah O(n + m) dan ruang ialah O(n + m).”

Penyelaman Mendalam Langkah demi Langkah

Mulakan dengan garis dasar yang betul tetapi perlahan. Bagi setiap sisi, abaikan ia buat sementara waktu dan lakukan traversal dari satu titik akhir. Jika titik akhir satu lagi tidak lagi boleh dicapai, sisi tersebut ialah bridge. Satu traversal mengambil masa O(n + m), jadi semua sisi mengambil masa O(m(n + m)). Kaedah ini munasabah untuk graf kecil atau pemeriksaan sekali sahaja kerana ia mudah diaudit, tetapi ia tidak dapat menampung skala yang diperlukan.

DFS mendedahkan semua laluan alternatif dalam satu laluan. Apabila satu nod u mula-mula dimasuki, tetapkan tin[u] = low[u] = timer dan tingkatkan timer. Jiran yang baru dilawati menjadi anak DFS. Jiran yang telah dilawati yang dicapai melalui sisi berbeza ialah sambungan bukan pokok, jadi ia boleh merendahkan low[u] kepada tin[neighbor]. Sebaik sahaja anak v selesai, keseluruhan subpokoknya telah diketahui, dan low[u] = min(low[u], low[v]) menyebarkan kebolehcapaian tersebut ke atas.

Perbandingan yang ketat ini penting. Jika low[v] < tin[u], subpokok anak mencapai leluhur kepada u. Jika low[v] == tin[u], ia mencapai u itu sendiri melalui laluan lain. Kedua-dua kes bermaksud sisi pokok [u, v] terletak pada satu kitaran. Hanya low[v] > tin[u] membuktikan bahawa setiap laluan dari subpokok anak ke bahagian yang telah ditemui menggunakan [u, v].

Pelaksanaan lelaran menyimpan nextIndex[u], iaitu entri kejiranan seterusnya yang masih perlu diperiksa. Nod kekal berada di atas tindanan semasa anak-anaknya berjalan. Apabila semua entri kejiranannya telah digunakan, nod itu dikeluarkan (popped); peristiwa tersebut mensimulasikan pengembalian daripada panggilan rekursif dan merupakan saat yang tepat untuk mengemas kini induknya.

type AdjacentEdge = readonly [to: number, edgeId: number]

function findCriticalConnections(
  n: number,
  connections: ReadonlyArray<readonly [number, number]>,
): number[][] {
  const graph: AdjacentEdge[][] = Array.from({ length: n }, () => [])

  connections.forEach(([from, to], edgeId) => {
    graph[from].push([to, edgeId])
    graph[to].push([from, edgeId])
  })

  const tin = new Array<number>(n).fill(-1)
  const low = new Array<number>(n).fill(-1)
  const parent = new Array<number>(n).fill(-1)
  const parentEdge = new Array<number>(n).fill(-1)
  const nextIndex = new Array<number>(n).fill(0)
  const bridges: number[][] = []
  let timer = 0

  for (let root = 0; root < n; root += 1) {
    if (tin[root] !== -1) continue

    tin[root] = timer
    low[root] = timer
    timer += 1
    const stack = [root]

    while (stack.length > 0) {
      const node = stack[stack.length - 1]

      if (nextIndex[node] < graph[node].length) {
        const [neighbor, edgeId] = graph[node][nextIndex[node]]
        nextIndex[node] += 1

        if (edgeId === parentEdge[node]) continue

        if (tin[neighbor] === -1) {
          parent[neighbor] = node
          parentEdge[neighbor] = edgeId
          tin[neighbor] = timer
          low[neighbor] = timer
          timer += 1
          stack.push(neighbor)
        } else {
          low[node] = Math.min(low[node], tin[neighbor])
        }
      } else {
        stack.pop()
        const parentNode = parent[node]

        if (parentNode !== -1) {
          if (low[node] > tin[parentNode]) {
            bridges.push([parentNode, node])
          }
          low[parentNode] = Math.min(low[parentNode], low[node])
        }
      }
    }
  }

  return bridges
}

Gelung luar adalah lewah untuk input asas yang bersambung tetapi memulakan DFS dengan betul dalam setiap komponen sekiranya jaminan tersebut ditarik balik. ID sisi lebih teguh berbanding melangkau mengikut nod induk. Dengan dua sisi selari antara u dan v, anak hanya melangkau sisi pokok; sisi kedua dilihat sebagai laluan alternatif dan merendahkan nilai low miliknya.

Untuk ketepatannya, pertimbangkan satu sisi pokok DFS u -> v selepas v selesai. Berdasarkan definisi low[v], nilai paling banyak tin[u] membuktikan laluan bukan pokok daripada subpokok v ke u atau leluhur. Digabungkan dengan laluan pokok, laluan itu membentuk satu kitaran yang mengandungi [u, v], jadi penyingkiran tidak boleh memisahkan subpokok tersebut. Jika low[v] > tin[u], tiada laluan sedemikian wujud. Setiap laluan dari subpokok tersebut ke bahagian yang ditemui sebelum ini mesti merentasi [u, v], jadi penyingkirannya meningkatkan bilangan komponen. Oleh itu, syarat ini adalah perlu dan mencukupi.

Setiap sisi tidak berarah muncul dua kali dalam senarai kejiranan, dan setiap entri diperiksa sekali. Setiap nod dimasukkan (pushed) dan dikeluarkan (popped) sekali. Masa ialah O(n + m). Graf, tatasusunan, tindanan, dan output menggunakan ruang O(n + m); tidak termasuk graf dan jawapan yang dikembalikan, ruang tambahan ialah O(n).

Ujian persaingan (adversarial) harus membandingkan set sisi ternormal, kerana susunan hasil tidak ditentukan. Satu sisi tunggal mestilah satu bridge; satu kitaran tidak boleh mempunyai sebarang bridge; setiap sisi pokok mestilah satu bridge; dan dua kitaran yang dicantumkan oleh satu sisi mesti melaporkan hanya penyambung tersebut. Uji juga rantai 100,000 nod untuk mendedahkan risiko tindanan rekursif. Untuk keyakinan tambahan, hasilkan graf rawak kecil dan bandingkan algoritma linear dengan garis dasar singkir-satu-sisi.

Contoh Jawapan Berkualiti Tinggi

“Penyelesaian terus menyingkirkan setiap sisi dan menjalankan semula traversal, tetapi itu memerlukan masa O(m(n + m)). Saya boleh menggunakan semula satu DFS dengan merekodkan masa penemuan dan masa penemuan terawal yang boleh dicapai daripada setiap subpokok DFS.

Apabila saya memasuki nod u, saya memulakan tin[u] dan low[u] kepada pemasa semasa. Anak pokok diproses sepenuhnya sebelum nilai low miliknya disebarkan kepada u. Bagi jiran yang telah dilawati yang dicapai oleh sisi berbeza, saya mengemas kini dengan tin jiran tersebut, kerana sisi itu sendiri ialah satu laluan keluar bukan pokok yang diwakili oleh invarian.

Selepas anak v selesai, [u, v] ialah satu bridge tepat apabila low[v] > tin[u]. Kesamaan tidak mencukupi: ia bermaksud subpokok mempunyai laluan lain kembali ke u, jadi sisi tersebut tergolong dalam satu kitaran. Nilai yang lebih besar bermaksud tiada nod dalam subpokok yang boleh mencapai u atau leluhur tanpa menggunakan sisi pokok, dan penyingkirannya memisahkan subpokok tersebut.

Saya akan melaksanakan DFS secara lelaran untuk had 100,000 nod. Tindanan mengekalkan nod sehingga setiap entri kejiranan telah diproses, yang memberi saya peristiwa kembali untuk menyebarkan nilai low anak. Saya juga menyimpan ID sisi induk dan melangkau tepat sisi tersebut. Ini mengendalikan soalan susulan sisi selari dengan betul. Setiap entri kejiranan diperiksa sekali, jadi masa ialah O(n + m) dan jumlah ruang ialah O(n + m). Saya akan menguji kitaran, pokok, dua kitaran dengan satu penyambung, rantai panjang, komponen tidak bersambung, dan sisi selari, kemudian melakukan ujian perbezaan (differential-test) graf rawak kecil terhadap garis dasar.”

Kesilapan Biasa

• Menjalankan semula DFS untuk setiap sisi → ketepatan tidak terjejas tetapi kes terburuk adalah kuadratik atau lebih buruk →

Gunakan satu DFS dan kekalkan maklumat laluan alternatif dalam low.

• Memeriksa low[child] >= tin[parent] → kesamaan sudah membuktikan laluan lain kembali ke

induk → Gunakan syarat ketat low[child] > tin[parent].

• Mengemas kini jiran yang dilawati dengan low[neighbor] → kebolehcapaian dari subpokok DFS lain bocor

merentasi sisi bukan pokok dan boleh menyembunyikan bridge sebenar → **Gunakan tin[neighbor] untuk jiran yang telah dilawati dan low[child] hanya selepas anak pokok selesai.**

• Melangkau setiap sisi ke nod induk → semua sisi selari diabaikan dan satu daripadanya mungkin dilaporkan

sebagai bridge → Tetapkan ID sisi dan langkau hanya sisi yang digunakan untuk memasuki nod.

• Menguji bridge sebelum anak selesai → laluan alternatif anak belum diketahui →

Nilaikan syarat semasa fasa pulangan simulasi.

• Bermula hanya pada nod 0 → soalan susulan graf tidak bersambung akan kehilangan komponen lain → **Mulakan dari setiap

nod yang masih belum dilawati.**

• Menggunakan rekursi tanpa memeriksa had tindanan → rantai yang panjang boleh gagal walaupun

kerumitannya linear → Gunakan tindanan eksplisit atau buktikan bahawa runtime menyokong kedalaman yang diperlukan.

Soalan Susulan dan Maklum Balas

Soalan Susulan 1: Apakah yang berubah jika graf tidak bersambung?

Takrifkan bridge sebagai sisi yang penyingkirannya meningkatkan jumlah komponen bersambung. Syarat low-link yang sama digunakan di dalam setiap komponen. Mulakan DFS dari setiap nod yang masa penemuannya masih -1; pelaksanaan yang disediakan sudah melakukan ini. Jangan memerlukan keseluruhan graf menjadi tidak bersambung selepas penyingkiran.

Soalan Susulan 2: Bagaimana jika sisi selari dan gelung sendiri dibenarkan?

Simpan ID unik untuk setiap sisi dan langkau hanya parentEdge[node]. Sisi kedua ke induk kemudian bertindak sebagai laluan bukan pokok, menghalang mana-mana sisi selari daripada diklasifikasikan sebagai bridge. Gelung sendiri mengemas kini nod dengan masa penemuannya sendiri dan tidak boleh menjadi bridge. Prom asas mengecualikan kedua-dua kes, tetapi identiti sisi pelaksanaan memberikan lanjutan yang betul.

Soalan Susulan 3: Bagaimanakah anda mengembalikan articulation point sebagai ganti?

Data low-link boleh digunakan semula, tetapi syaratnya beralih daripada sisi kepada bucu (vertice). Nod bukan punca u ialah satu articulation point apabila ia mempunyai anak DFS v dengan low[v] >= tin[u]. Punca DFS ialah articulation point hanya apabila ia mempunyai sekurang-kurangnya dua anak pokok DFS. Perhatikan bahawa kesamaan tergolong dalam syarat bucu, manakala pengesanan bridge menggunakan > yang ketat.

Soalan Susulan 4: Apakah yang berubah apabila sisi ditambah secara berterusan?

Algoritma ini menjawab snapshot statik dalam masa linear. Pengiraan semula selepas setiap sisipan memerlukan kos O(n + m) bagi setiap kemas kini. Beban kerja sisipan sahaja boleh mengekalkan maklumat bridge dengan struktur data dalam talian (online) yang khusus; penambahan dan pemadaman sewenang-wenangnya memerlukan reka bentuk keterhubungan dinamik yang lebih umum. Jelaskan jenis kemas kini, kadar pertanyaan, dan keperluan ketekalan sebelum memilih satu penyelesaian.

Soalan Susulan 5: Bilakah garis dasar carian berulang masih menjadi jawapan yang lebih baik?

Untuk graf yang sangat kecil, satu sisi yang disyaki, atau kod diagnostik di mana kesederhanaan lebih penting daripada latensi, melangkau satu sisi dan menjalankan BFS adalah lebih pendek dan lebih mudah diperiksa. Nyatakan kos O(n + m) untuk satu sisi dan elakkan daripada memperkenalkan keadaan low-link melainkan tugasan tersebut benar-benar meminta semua bridge atau pertanyaan berulang.