Wawancara Koding: Temukan Semua Critical Connection dalam Jaringan

Prompt dan Konteks yang Berlaku

Anda diberikan n node yang diberi label 0 hingga n - 1 dan sebuah array connections, di mana setiap pasangan [u, v] merupakan edge tak berarah. Graf ini terhubung dan sederhana: tidak memiliki self-loop atau edge ganda. Kembalikan setiap critical connection, yang berarti setiap edge yang jika dihapus akan membuat graf terputus. Jawaban boleh dalam urutan apa pun, dan urutan endpoint mana pun dapat diterima.

Asumsikan 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 edge pertama membentuk sebuah siklus, sehingga menghapus salah satunya tetap menyisakan rute alternatif. Node 3 hanya memiliki edge [1, 3]; menghapusnya akan memisahkan node 3. Dalam terminologi graf, critical connection adalah sebuah bridge.

Ini adalah pertanyaan koding tentang invarian graf. Soal ini berbeda dari artikel Union-Find yang sudah ada, yang memelihara komponen terhubung saat edge ditambahkan; berbeda dari topological sorting, yang mengurutkan graf asiklik berarah; dan berbeda dari Dijkstra, yang mengoptimalkan panjang jalur berbobot. Di sini output bergantung pada bagaimana konektivitas berubah setelah menghapus setiap edge tak berarah.

Hal yang Dievaluasi Pewawancara

Sinyal pertama adalah apakah kandidat menolak pendekatan pencarian berulang yang jelas pada skala yang disebutkan. Menghapus satu edge dan menjalankan BFS atau DFS menjawab satu kueri dengan benar, tetapi mengulanginya untuk semua m edge membutuhkan waktu O(m(n + m)). Pada 100.000 edge, traversal linear per edge tidak memungkinkan.

Sinyal kedua adalah invarian low-link yang presisi. Waktu penemuan DFS tin[u] mencatat kapan u pertama kali dikunjungi. low[u] adalah waktu penemuan paling awal yang dapat dijangkau dari subtree DFS milik u dengan menuruni tree edge dan kemudian menggunakan paling banyak satu non-tree edge. Untuk sebuah DFS tree edge u -> v, edge tersebut adalah sebuah bridge tepat ketika low[v] > tin[u].

Sinyal ketiga adalah disiplin implementasi. Pada tetangga yang sudah dikunjungi, perbarui dengan tin[neighbor], bukan low[neighbor]. Lewati edge persis yang digunakan untuk memasuki sebuah node, bukan setiap edge yang endpoint lainnya sama dengan parent. ID edge membuat pembedaan tersebut eksplisit dan menjaga kode tetap benar jika pertanyaan lanjutan mengizinkan edge paralel.

Sinyal keempat adalah kesadaran bahasa tingkat produksi. DFS rekursif ringkas, tetapi rantai sepanjang 100.000 node dapat melampaui batas call-stack runtime JavaScript. DFS iteratif harus menyimulasikan fase masuk dan fase kembali-dari-child sehingga dapat mempropagasi nilai low hanya setelah child selesai diproses.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Apakah grafnya berarah? Tidak. Bridge dalam graf berarah memerlukan definisi dan

algoritma yang berbeda.

• Apakah grafnya dijamin terhubung? Ya untuk prompt dasar. Mengiterasi setiap

node yang belum dikunjungi tidak memakan biaya asimtotik tambahan dan membuat implementasi berfungsi untuk pertanyaan lanjutan graf terputus juga.

• Apakah edge ganda diperbolehkan? Tidak pada prompt dasar. Implementasi tetap memberikan ID untuk setiap

edge, sehingga dua edge paralel akan dengan benar menyediakan rute alternatif alih-alih keduanya dilaporkan sebagai bridge.

• Bolehkah hasilnya menggunakan urutan endpoint mana pun? Ya. Jika sistem pengujian membutuhkan output kanonikal, normalisasi

setiap edge ke [min, max] dan urutkan hanya setelah menemukan bridge.

• Apakah grafnya statis? Ya. Memelihara bridge saat edge disisipkan atau dihapus adalah masalah konektivitas

dinamis; menjalankan ulang algoritma linear ini setelah setiap pembaruan mungkin terlalu mahal.

• Bisakah saya menggunakan rekursi? Hanya jika lingkungan menjamin kedalaman stack yang cukup. Dengan n hingga

100.000 di JavaScript atau TypeScript, stack eksplisit adalah kontrak yang lebih aman.

Kerangka Jawaban 30 Detik

“Saya akan menjalankan DFS sekali dan menetapkan waktu penemuan tin untuk setiap node. Untuk setiap node, low mencatat waktu penemuan paling awal yang dapat dijangkau dari subtree DFS-nya tanpa kembali melalui tree edge persis yang memasukinya. Setelah sebuah child v selesai, jika low[v] > tin[u], subtree di bawah v tidak memiliki rute ke u atau leluhurnya, jadi [u, v] adalah sebuah bridge. Jika tidak, sebuah back edge menyediakan rute alternatif. Saya akan menggunakan ID edge dan stack DFS eksplisit untuk menangani pertanyaan lanjutan edge paralel dan menghindari call-stack overflow. Setiap entri ketetanggaan diproses sekali, jadi waktunya adalah O(n + m) dan ruangnya adalah O(n + m).”

Penjelasan Mendalam Langkah demi Langkah

Mulai dengan baseline yang benar tetapi lambat. Untuk setiap edge, abaikan sementara dan lakukan traversal dari satu endpoint. Jika endpoint lainnya menjadi tidak terjangkau, edge tersebut adalah bridge. Satu traversal membutuhkan O(n + m), sehingga semua edge membutuhkan O(m(n + m)). Metode ini bisa masuk akal untuk graf kecil atau pemeriksaan sekali jalan karena mudah diaudit, tetapi tidak memenuhi skala yang dibutuhkan.

DFS mengekspos semua rute alternatif dalam satu kali jalan. Ketika sebuah node u pertama kali dimasuki, tetapkan tin[u] = low[u] = timer dan inkremen timer. Tetangga yang baru dikunjungi menjadi DFS child. Tetangga yang sudah dikunjungi yang dijangkau melalui edge berbeda adalah koneksi non-tree, sehingga dapat menurunkan low[u] ke tin[neighbor]. Setelah child v selesai, seluruh subtree-nya telah diketahui, dan low[u] = min(low[u], low[v]) mempropagasi keterjangkauan tersebut ke atas.

Perbandingan ketat ini penting. Jika low[v] < tin[u], subtree child menjangkau leluhur dari u. Jika low[v] == tin[u], ia menjangkau u itu sendiri melalui rute lain. Kedua kasus berarti tree edge [u, v] terletak pada sebuah siklus. Hanya low[v] > tin[u] yang membuktikan bahwa setiap rute dari subtree child ke sisi yang sudah ditemukan sebelumnya menggunakan [u, v].

Implementasi iteratif menyimpan nextIndex[u], entri ketetanggaan berikutnya yang masih harus diperiksa. Node tetap berada di stack saat child-nya berjalan. Ketika semua entri ketetanggaannya habis, node di-pop; peristiwa tersebut menyimulasikan pengembalian dari pemanggilan rekursif dan merupakan momen yang tepat untuk memperbarui parent-nya.

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
}

Loop luar redundan untuk input dasar yang terhubung tetapi dengan benar memulai DFS di setiap komponen jika jaminan tersebut dihilangkan. ID edge lebih tangguh daripada melewati berdasarkan node parent. Dengan dua edge paralel antara u dan v, child hanya melewati tree edge; edge kedua dilihat sebagai rute alternatif dan menurunkan nilai low miliknya.

Untuk kebenarannya, perhatikan sebuah DFS tree edge u -> v setelah v selesai. Berdasarkan definisi low[v], nilai paling banyak tin[u] membuktikan adanya rute non-tree dari subtree milik v ke u atau leluhur. Dikombinasikan dengan tree path, rute tersebut membentuk siklus yang memuat [u, v], sehingga penghapusan tidak dapat memisahkan subtree. Jika low[v] > tin[u], tidak ada rute seperti itu. Setiap jalur dari subtree tersebut ke bagian yang ditemukan sebelumnya harus melintasi [u, v], sehingga menghapusnya akan menambah jumlah komponen. Oleh karena itu, kondisi ini bersifat perlu sekaligus cukup.

Setiap edge tak berarah muncul dua kali dalam adjacency list, dan setiap entri diperiksa sekali. Setiap node di-push dan di-pop sekali. Waktu eksekusinya adalah O(n + m). Graf, array, stack, dan output menggunakan ruang O(n + m); di luar graf dan jawaban yang dikembalikan, auxiliary space adalah O(n).

Pengujian adversarial harus membandingkan set edge yang telah dinormalisasi, karena urutan hasil tidak ditentukan. Sebuah edge tunggal harus menjadi bridge; sebuah siklus tidak boleh memiliki bridge; setiap edge pada tree harus berupa bridge; dan dua siklus yang dihubungkan oleh satu edge harus melaporkan hanya edge penghubung tersebut. Uji juga rantai 100.000 node untuk mengekspos risiko rekursif stack. Untuk keyakinan ekstra, buat graf acak kecil dan bandingkan algoritma linear dengan baseline hapus-satu-edge.

Contoh Jawaban Berkualitas Tinggi

“Solusi langsung adalah menghapus setiap edge dan menjalankan ulang traversal, tetapi itu memakan biaya O(m(n + m)). Saya dapat menggunakan kembali satu DFS dengan mencatat waktu penemuan dan waktu penemuan paling awal yang dapat dijangkau dari setiap subtree DFS.

Saat saya memasuki node u, saya menginisialisasi tin[u] dan low[u] ke timer saat ini. Tree child diproses sepenuhnya sebelum nilai low miliknya dipropagasi ke u. Untuk tetangga yang sudah dikunjungi yang dijangkau oleh edge berbeda, saya memperbarui dengan tin tetangga tersebut, karena edge itu sendiri adalah satu-satunya jalur keluar non-tree yang direpresentasikan oleh invarian.

Setelah child v selesai, [u, v] adalah bridge tepat ketika low[v] > tin[u]. Kesamaan nilai tidak cukup: itu berarti subtree memiliki rute lain kembali ke u, sehingga edge tersebut termasuk dalam siklus. Nilai yang lebih besar berarti tidak ada node di subtree yang dapat menjangkau u atau leluhur tanpa menggunakan tree edge, dan menghapusnya akan memisahkan subtree.

Saya akan mengimplementasikan DFS secara iteratif untuk batasan 100.000 node. Stack menahan sebuah node sampai setiap entri ketetanggaan selesai diproses, yang memberi saya event return untuk mempropagasi nilai low milik child. Saya juga menyimpan ID edge parent dan melewati persis edge tersebut. Ini menangani pertanyaan lanjutan terkait edge paralel dengan benar. Setiap entri ketetanggaan diperiksa sekali, sehingga waktu eksekusinya adalah O(n + m) dan total ruang adalah O(n + m). Saya akan menguji siklus, tree, dua siklus dengan satu penghubung, rantai panjang, komponen terputus, dan edge paralel, lalu melakukan differential-test pada graf acak kecil terhadap baseline.”

Kesalahan Umum

• Menjalankan ulang DFS untuk setiap edge → kebenaran tidak masalah tetapi kasus terburuknya adalah kuadratik atau lebih buruk →

Gunakan satu DFS dan pertahankan informasi rute alternatif dalam low.

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

parent → Gunakan kondisi ketat low[child] > tin[parent].

• Memperbarui tetangga yang sudah dikunjungi dengan low[neighbor] → keterjangkauan dari subtree DFS lain bocor

melalui non-tree edge dan dapat menyembunyikan bridge yang sebenarnya → **Gunakan tin[neighbor] untuk tetangga yang sudah dikunjungi dan low[child] hanya setelah tree child selesai.**

• Melewati setiap edge ke node parent → semua edge paralel diabaikan dan salah satunya mungkin dilaporkan

sebagai bridge → Tetapkan ID edge dan lewati hanya edge yang digunakan untuk memasuki node.

• Menguji bridge sebelum child selesai → rute alternatif child belum diketahui →

Evaluasi kondisi selama fase simulasi return.

• Hanya memulai di node 0 → pertanyaan lanjutan dengan graf terputus akan kehilangan komponen lain → **Mulai dari setiap

node yang masih belum dikunjungi.**

• Menggunakan rekursi tanpa memeriksa batas stack → rantai yang panjang bisa gagal meskipun

kompleksitasnya linear → Gunakan stack eksplisit atau buktikan bahwa runtime mendukung kedalaman yang diperlukan.

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan Lanjutan 1: Apa yang berubah jika grafnya terputus?

Definisikan bridge sebagai edge yang jika dihapus akan menambah jumlah total komponen terhubung. Kondisi low-link yang sama berlaku di dalam setiap komponen. Mulai DFS dari setiap node yang waktu penemuannya masih -1; implementasi yang disediakan sudah melakukan ini. Jangan mengharuskan seluruh graf menjadi terputus setelah penghapusan.

Pertanyaan Lanjutan 2: Bagaimana jika edge paralel dan self-loop diizinkan?

Pertahankan ID unik untuk setiap edge dan lewati hanya parentEdge[node]. Edge kedua ke parent kemudian berfungsi sebagai rute non-tree, mencegah kedua edge paralel diklasifikasikan sebagai bridge. Self-loop memperbarui sebuah node dengan waktu penemuannya sendiri dan tidak akan pernah bisa menjadi bridge. Prompt dasar mengecualikan kedua kasus tersebut, tetapi identitas edge pada implementasi ini memberikan ekstensi yang tepat.

Pertanyaan Lanjutan 3: Bagaimana jika Anda diminta mengembalikan articulation point sebagai gantinya?

Data low-link dapat digunakan kembali, tetapi kondisinya berpindah dari edge ke simpul (vertex). Node non-akar u adalah sebuah articulation point ketika ia memiliki DFS child v dengan low[v] >= tin[u]. Akar DFS adalah sebuah articulation point hanya ketika ia memiliki setidaknya dua child pada DFS-tree. Perhatikan bahwa tanda kesamaan berlaku pada kondisi simpul, sedangkan deteksi bridge menggunakan kondisi ketat >.

Pertanyaan Lanjutan 4: Apa yang berubah ketika edge ditambahkan secara terus-menerus?

Algoritma ini menjawab snapshot statis dalam waktu linear. Menghitung ulang setelah setiap penyisipan membutuhkan biaya O(n + m) per pembaruan. Beban kerja insertion-only dapat memelihara informasi bridge dengan struktur data online khusus; penambahan dan penghapusan sembarang memerlukan rancangan dynamic-connectivity yang lebih umum. Klarifikasi jenis pembaruan, laju kueri, dan persyaratan konsistensi sebelum memilih salah satunya.

Pertanyaan Lanjutan 5: Kapan baseline pencarian berulang masih menjadi jawaban yang lebih baik?

Untuk graf yang sangat kecil, satu edge yang dicurigai, atau kode diagnostik di mana kesederhanaan lebih diprioritaskan daripada latensi, melewati satu edge dan menjalankan BFS lebih singkat serta lebih mudah diperiksa. Nyatakan biaya O(n + m) untuk satu edge dan hindari memperkenalkan state low-link kecuali jika tugas tersebut benar-benar meminta semua bridge atau kueri berulang.