कोडिंग इंटरव्यू: नेटवर्क में सभी क्रिटिकल कनेक्शन्स (Critical Connections) खोजें

प्रॉम्प्ट और लागू संदर्भ

आपको 0 से n - 1 तक लेबल किए गए n नोड्स और एक ऐरे connections दिया गया है, जहाँ प्रत्येक जोड़ी [u, v] एक अनडायरेक्टेड किनारा (undirected edge) है। ग्राफ जुड़ा हुआ और सरल है: इसमें कोई सेल्फ-लूप या दोहराए गए किनारे नहीं हैं। प्रत्येक क्रिटिकल कनेक्शन लौटाएं, जिसका अर्थ है वह प्रत्येक किनारा जिसे हटाने पर ग्राफ डिस्कनेक्ट हो जाता है। उत्तर किसी भी क्रम में हो सकता है, और किसी भी एंडपॉइंट क्रम को स्वीकार किया जाता है।

मान लें 2 <= n <= 100000 और n - 1 <= connections.length <= 100000। उदाहरण के लिए:

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

पहले तीन किनारे एक चक्र (cycle) बनाते हैं, इसलिए उनमें से किसी एक को हटाने पर भी एक वैकल्पिक मार्ग बचता है। नोड 3 के पास केवल [1, 3] किनारा है; इसे हटाने पर नोड 3 अलग हो जाता है। ग्राफ शब्दावली में, एक क्रिटिकल कनेक्शन को ब्रिज (bridge) कहा जाता है।

यह ग्राफ इनवेरिएंट्स (graph invariants) के बारे में एक कोडिंग प्रश्न है। यह मौजूदा Union-Find लेख से भिन्न है, जो किनारे जोड़े जाने पर कनेक्टेड कॉम्पोनेंट्स को बनाए रखता है; यह टोपोलॉजिकल सॉर्टिंग से भिन्न है, जो एक डायरेक्टेड एसाइक्लिक ग्राफ को क्रमित करता है; और यह Dijkstra से भिन्न है, जो वेटेड पाथ लंबाई को ऑप्टिमाइज़ करता है। यहाँ आउटपुट इस बात पर निर्भर करता है कि प्रत्येक अनडायरेक्टेड किनारे को हटाने के बाद कनेक्टिविटी कैसे बदलती है।

इंटरव्यूअर क्या मूल्यांकन करता है

पहला संकेत यह है कि क्या उम्मीदवार दिए गए पैमाने पर स्पष्ट रिपीटेड-सर्च (repeated-search) दृष्टिकोण को अस्वीकार करता है या नहीं। एक किनारे को हटाना और BFS या DFS चलाना एक क्वेरी का सही उत्तर देता है, लेकिन सभी m किनारों के लिए इसे दोहराने में O(m(n + m)) समय लगता है। 100,000 किनारों पर, प्रति किनारा एक लीनियर ट्रैवर्सल व्यावहारिक नहीं है।

दूसरा संकेत एक सटीक लो-लिंक इनवेरिएंट है। एक DFS डिस्कवरी समय tin[u] यह रिकॉर्ड करता है कि u को पहली बार कब विज़िट किया गया था। low[u] वह सबसे प्रारंभिक डिस्कवरी समय है जो u के DFS सब-ट्री से ट्री किनारों पर नीचे जाकर और फिर अधिकतम एक गैर-ट्री किनारे का उपयोग करके पहुँचा जा सकता है। एक DFS ट्री किनारे u -> v के लिए, वह किनारा ठीक तब एक ब्रिज होता है जब low[v] > tin[u]।

तीसरा संकेत कार्यान्वयन अनुशासन (implementation discipline) है। पहले से विज़िट किए गए पड़ोसी पर, tin[neighbor] से अपडेट करें, low[neighbor] से नहीं। किसी नोड में प्रवेश करने के लिए उपयोग किए गए सटीक किनारे को छोड़ें, न कि उस प्रत्येक किनारे को जिसका दूसरा एंडपॉइंट पैरेंट के बराबर है। एज आईडी (Edge IDs) उस अंतर को स्पष्ट बनाती हैं और यदि फॉलो-अप में समानांतर किनारों (parallel edges) की अनुमति है, तो कोड को सही रखती हैं।

चौथा संकेत प्रोडक्शन-लैंग्वेज अवेयरनेस है। एक रिकर्सिव DFS संक्षिप्त होता है, लेकिन 100,000 नोड्स की एक श्रृंखला JavaScript रनटाइम की कॉल-स्टैक सीमा को पार कर सकती है। एक इटरेटिव DFS को एंट्री फेज़ और रिटर्न-फ्रॉम-चाइल्ड फेज़ दोनों का अनुकरण करना चाहिए ताकि यह low मानों को केवल तभी प्रोपेगेट कर सके जब एक चाइल्ड समाप्त हो गया हो।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• क्या ग्राफ डायरेक्टेड है? नहीं। डायरेक्टेड ग्राफ में ब्रिज की एक अलग परिभाषा और एल्गोरिदम की आवश्यकता होती है।
• क्या ग्राफ के जुड़े होने की गारंटी है? बेस प्रॉम्प्ट के लिए हाँ। प्रत्येक अनविज़िटेड नोड पर पुनरावृति करने में एसिम्प्टोटिक रूप से कुछ अतिरिक्त खर्च नहीं होता है और यह कार्यान्वयन को डिस्कनेक्टेड फॉलो-अप के लिए भी कार्य करने योग्य बनाता है।
• क्या दोहराए गए किनारों (parallel edges) की अनुमति है? बेस प्रॉम्प्ट में नहीं। कार्यान्वयन अभी भी प्रत्येक किनारे को एक आईडी देता है, इसलिए दो समानांतर किनारे दोनों को ब्रिज के रूप में रिपोर्ट किए जाने के बजाय सही ढंग से वैकल्पिक मार्ग प्रदान करेंगे।
• क्या परिणाम किसी भी एंडपॉइंट क्रम का उपयोग कर सकता है? हाँ। यदि कोई जज कैनोनिकल आउटपुट की मांग करता है, तो प्रत्येक किनारे को [min, max] में सामान्यीकृत (normalize) करें और ब्रिज खोजने के बाद ही सॉर्ट करें।
• क्या ग्राफ स्थिर (static) है? हाँ। किनारे डाले या हटाए जाने के दौरान ब्रिजेस को बनाए रखना एक डायनेमिक कनेक्टिविटी समस्या है; प्रत्येक अपडेट के बाद इस लीनियर एल्गोरिदम को दोबारा चलाना बहुत महंगा हो सकता है।
• क्या मैं रिकर्सन का उपयोग कर सकता हूँ? केवल तभी जब वातावरण पर्याप्त स्टैक डेप्थ की गारंटी देता हो। JavaScript या TypeScript में n के 100,000 तक होने पर, एक स्पष्ट स्टैक (explicit stack) अधिक सुरक्षित अनुबंध है।

30-सेकंड उत्तर फ्रेमवर्क

"मैं एक बार DFS चलाऊंगा और प्रत्येक नोड को एक डिस्कवरी समय tin असाइन करूंगा। प्रत्येक नोड के लिए, low उसके DFS सब-ट्री से उस सटीक ट्री किनारे से वापस जाए बिना पहुँच योग्य सबसे प्रारंभिक डिस्कवरी समय को रिकॉर्ड करता है जिससे इसमें प्रवेश किया गया था। चाइल्ड v के समाप्त होने के बाद, यदि low[v] > tin[u] है, तो v के अंतर्गत सब-ट्री के पास u या किसी पूर्वज (ancestor) तक कोई मार्ग नहीं है, इसलिए [u, v] एक ब्रिज है। अन्यथा एक बैक-एज एक वैकल्पिक मार्ग प्रदान करता है। मैं पैरेलल-एज फॉलो-अप को संभालने और कॉल-स्टैक ओवरफ्लो से बचने के लिए एज आईडी और एक स्पष्ट DFS स्टैक का उपयोग करूंगा। प्रत्येक एडजसेंसी प्रविष्टि को एक बार प्रोसेस किया जाता है, इसलिए समय O(n + m) है और स्पेस O(n + m) है।"

चरण-दर-चरण गहन विश्लेषण

सही लेकिन धीमी बेसलाइन से शुरुआत करें। प्रत्येक किनारे के लिए, इसे अस्थायी रूप से अनदेखा करें और एक एंडपॉइंट से ट्रैवर्सल करें। यदि दूसरा एंडपॉइंट अगम्य हो जाता है, तो वह किनारा एक ब्रिज है। एक ट्रैवर्सल में O(n + m) लगता है, इसलिए सभी किनारों में O(m(n + m)) लगता है। यह विधि एक छोटे ग्राफ या वन-ऑफ जांच के लिए उचित हो सकती है क्योंकि इसका ऑडिट करना आसान है, लेकिन यह आवश्यक पैमाने से चूक जाती है।

DFS एक ही पास में सभी वैकल्पिक मार्गों को उजागर करता है। जब किसी नोड u में पहली बार प्रवेश किया जाता है, तो tin[u] = low[u] = timer असाइन करें और timer को बढ़ाएं। एक नया विज़िट किया गया पड़ोसी DFS चाइल्ड बन जाता है। एक अलग किनारे के माध्यम से पहुँचा गया पहले से विज़िट किया गया पड़ोसी एक गैर-ट्री कनेक्शन है, इसलिए यह low[u] को tin[neighbor] तक कम कर सकता है। एक बार चाइल्ड v समाप्त हो जाने पर, उसका पूरा सब-ट्री ज्ञात हो जाता है, और low[u] = min(low[u], low[v]) उस पहुंच योग्यता (reachability) को ऊपर की ओर प्रोपेगेट करता है।

सख्त तुलना (strict comparison) मायने रखती है। यदि low[v] < tin[u] है, तो चाइल्ड सब-ट्री u के पूर्वज तक पहुँचता है। यदि low[v] == tin[u] है, तो यह दूसरे मार्ग से स्वयं u तक पहुँचता है। दोनों मामलों का अर्थ है कि ट्री किनारा [u, v] एक चक्र पर स्थित है। केवल low[v] > tin[u] ही यह सिद्ध करता है कि चाइल्ड सब-ट्री से पहले से खोजे गए हिस्से तक का प्रत्येक मार्ग [u, v] का उपयोग करता है।

एक इटरेटिव कार्यान्वयन nextIndex[u] को संग्रहीत करता है, जो अगली एडजसेंसी प्रविष्टि है जिसे अभी जांचा जाना बाकी है। जब तक उसके बच्चे चलते हैं, नोड स्टैक पर बना रहता है। जब इसकी सभी एडजसेंसी प्रविष्टियाँ समाप्त हो जाती हैं, तो इसे पॉप कर दिया जाता है; वह घटना रिकर्सिव कॉल से लौटने का अनुकरण करती है और इसके पैरेंट को अपडेट करने का सही समय है।

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
}

बाहरी लूप कनेक्टेड बेस इनपुट के लिए अनावश्यक है, लेकिन यदि वह गारंटी हटा दी जाती है तो यह प्रत्येक कॉम्पोनेंट में सही ढंग से DFS शुरू करता है। पैरेंट नोड द्वारा स्किप करने की तुलना में एज आईडी अधिक मजबूत हैं। u और v के बीच दो समानांतर किनारों के साथ, चाइल्ड केवल ट्री किनारे को छोड़ता है; दूसरा किनारा एक वैकल्पिक मार्ग के रूप में देखा जाता है और इसके low मान को कम करता है।

शुद्धता के लिए, v के समाप्त होने के बाद एक DFS ट्री किनारे u -> v पर विचार करें। low[v] की परिभाषा के अनुसार, अधिकतम tin[u] का मान v के सब-ट्री से u या किसी पूर्वज तक एक गैर-ट्री मार्ग का प्रमाण है। ट्री पाथ्स के साथ मिलकर, वह मार्ग [u, v] युक्त एक चक्र बनाता है, इसलिए इसे हटाने से सब-ट्री अलग नहीं हो सकता। यदि low[v] > tin[u] है, तो ऐसा कोई मार्ग मौजूद नहीं है। उस सब-ट्री से पहले खोजे गए हिस्से तक के प्रत्येक पथ को [u, v] को पार करना होगा, इसलिए इसे हटाने से कॉम्पोनेंट काउंट बढ़ जाता है। इसलिए यह शर्त आवश्यक और पर्याप्त दोनों है।

प्रत्येक अनडायरेक्टेड किनारा एडजसेंसी सूचियों में दो बार दिखाई देता है, और प्रत्येक प्रविष्टि का एक बार निरीक्षण किया जाता है। प्रत्येक नोड को एक बार पुश और पॉप किया जाता है। समय O(n + m) है। ग्राफ, ऐरे, स्टैक और आउटपुट O(n + m) स्पेस का उपयोग करते हैं; ग्राफ और लौटाए गए उत्तर को छोड़कर, सहायक स्पेस (auxiliary space) O(n) है।

प्रतिकूल परीक्षणों (adversarial tests) को सामान्यीकृत किनारा सेटों की तुलना करनी चाहिए, क्योंकि परिणाम का क्रम अनिर्दिष्ट है। एक एकल किनारा एक ब्रिज होना चाहिए; एक चक्र में कोई ब्रिज नहीं होना चाहिए; एक ट्री का प्रत्येक किनारा एक ब्रिज होना चाहिए; और एक किनारे से जुड़े दो चक्रों को केवल कनेक्टर की रिपोर्ट करनी चाहिए। रिकर्सिव स्टैक जोखिम को उजागर करने के लिए 100,000-नोड श्रृंखला का भी परीक्षण करें। अतिरिक्त विश्वास के लिए, छोटे यादृच्छिक (random) ग्राफ उत्पन्न करें और लीनियर एल्गोरिदम की तुलना रिमूव-वन-एज बेसलाइन से करें।

उच्च-गुणवत्ता वाला नमूना उत्तर

"एक प्रत्यक्ष समाधान प्रत्येक किनारे को हटाता है और एक ट्रैवर्सल को फिर से चलाता है, लेकिन इसमें O(m(n + m)) का खर्च आता है। मैं डिस्कवरी समय और प्रत्येक DFS सब-ट्री से पहुँच योग्य सबसे प्रारंभिक डिस्कवरी समय को रिकॉर्ड करके एक ही DFS का पुन: उपयोग कर सकता हूँ।

जब मैं नोड u में प्रवेश करता हूँ, तो मैं tin[u] और low[u] को वर्तमान टाइमर पर इनिशियलाइज़ करता हूँ। एक ट्री चाइल्ड को पूरी तरह से प्रोसेस किया जाता है इससे पहले कि उसका low मान u पर प्रोपेगेट हो। एक अलग किनारे से पहुँचे गए पहले से विज़िट किए गए पड़ोसी के लिए, मैं उस पड़ोसी के tin के साथ अपडेट करता हूँ, क्योंकि वह किनारा स्वयं इनवेरिएंट द्वारा दर्शाया गया एक गैर-ट्री एस्केप है।

चाइल्ड v के समाप्त होने के बाद, [u, v] ठीक तब एक ब्रिज होता है जब low[v] > tin[u]। समानता पर्याप्त नहीं है: इसका अर्थ है कि सब-ट्री के पास वापस u तक जाने का एक और मार्ग है, इसलिए किनारा एक चक्र से संबंधित है। एक बड़ा मान होने का अर्थ है कि सब-ट्री का कोई भी नोड ट्री किनारे का उपयोग किए बिना u या किसी पूर्वज तक नहीं पहुँच सकता है, और इसे हटाने पर सब-ट्री अलग हो जाता है।

मैं 100,000-नोड सीमा के लिए DFS को इटरेटिव रूप से लागू करूँगा। स्टैक तब तक एक नोड रखता है जब तक कि प्रत्येक एडजसेंसी प्रविष्टि संसाधित नहीं हो जाती, जो मुझे चाइल्ड के low मान को प्रोपेगेट करने के लिए एक रिटर्न इवेंट देता है। मैं पैरेंट एज आईडी भी संग्रहीत करता हूँ और केवल उसी किनारे को छोड़ता हूँ। यह पैरेलल-एज फॉलो-अप को सही ढंग से संभालता है। प्रत्येक एडजसेंसी प्रविष्टि का एक बार निरीक्षण किया जाता है, इसलिए समय O(n + m) है और कुल स्पेस O(n + m) है। मैं एक चक्र, एक ट्री, एक कनेक्टर वाले दो चक्र, एक लंबी श्रृंखला, डिस्कनेक्टेड कॉम्पोनेंट्स और समानांतर किनारों का परीक्षण करूँगा, फिर बेसलाइन के विरुद्ध छोटे यादृच्छिक ग्राफ का डिफ़रेंशियल-टेस्ट करूँगा।"

सामान्य गलतियाँ

• प्रत्येक किनारे के लिए DFS को दोबारा चलाना → शुद्धता ठीक है लेकिन सबसे खराब स्थिति द्विघात (quadratic) या उससे भी बदतर है → एक DFS का उपयोग करें और low में वैकल्पिक-मार्ग की जानकारी सुरक्षित रखें।
• low[child] >= tin[parent] की जाँच करना → समानता पहले से ही पैरेंट तक वापस जाने वाले किसी अन्य पथ का प्रमाण देती है → सख्त शर्त low[child] > tin[parent] का उपयोग करें।
• विज़िट किए गए पड़ोसी को low[neighbor] से अपडेट करना → दूसरे DFS सब-ट्री से पहुँच योग्यता एक गैर-ट्री किनारे के पार लीक हो जाती है और एक वास्तविक ब्रिज को छिपा सकती है → पहले से विज़िट किए गए पड़ोसी के लिए tin[neighbor] का उपयोग करें और low[child] का उपयोग केवल ट्री चाइल्ड के समाप्त होने के बाद करें।
• पैरेंट नोड के प्रत्येक किनारे को छोड़ना → समानांतर किनारों को पूरी तरह से अनदेखा कर दिया जाता है और किसी एक को ब्रिज के रूप में रिपोर्ट किया जा सकता है → एज आईडी असाइन करें और नोड में प्रवेश करने के लिए उपयोग किए गए केवल उसी किनारे को छोड़ें।
• चाइल्ड के समाप्त होने से पहले ब्रिज का परीक्षण करना → चाइल्ड के वैकल्पिक मार्ग अभी तक ज्ञात नहीं हैं → सिम्युलेटेड रिटर्न फेज़ के दौरान स्थिति का मूल्यांकन करें।
• केवल नोड 0 से शुरू करना → एक डिस्कनेक्टेड फॉलो-अप अन्य कॉम्पोनेंट्स को खो देता है → प्रत्येक अभी तक अनविज़िटेड नोड से शुरू करें।
• स्टैक सीमाओं की जाँच किए बिना रिकर्सन का उपयोग करना → लीनियर जटिलता के बावजूद एक लंबी श्रृंखला विफल हो सकती है → एक स्पष्ट स्टैक का उपयोग करें या सिद्ध करें कि रनटाइम आवश्यक गहराई का समर्थन करता है।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: यदि ग्राफ डिस्कनेक्टेड है तो क्या बदलता है?

एक ब्रिज को ऐसे किनारे के रूप में परिभाषित करें जिसके हटने से कनेक्टेड कॉम्पोनेंट्स की कुल संख्या बढ़ जाती है। वही लो-लिंक शर्त प्रत्येक कॉम्पोनेंट के अंदर लागू होती है। प्रत्येक नोड से DFS शुरू करें जिसका डिस्कवरी समय अभी भी -1 है; प्रदान किया गया कार्यान्वयन पहले से ही ऐसा करता है। यह आवश्यकता न रखें कि हटाने के बाद पूरा ग्राफ डिस्कनेक्ट हो जाए।

फॉलो-अप 2: क्या होगा यदि समानांतर किनारों और सेल्फ-लूप की अनुमति हो?

प्रत्येक किनारे के लिए एक अद्वितीय आईडी रखें और केवल parentEdge[node] को छोड़ें। पैरेंट के लिए एक दूसरा किनारा फिर एक गैर-ट्री मार्ग के रूप में कार्य करता है, जिससे किसी भी समानांतर किनारे को ब्रिज के रूप में वर्गीकृत होने से रोका जा सकता है। एक सेल्फ-लूप नोड को उसके अपने डिस्कवरी समय के साथ अपडेट करता है और कभी भी ब्रिज नहीं हो सकता है। बेस प्रॉम्प्ट दोनों मामलों को बाहर करता है, लेकिन कार्यान्वयन की एज आइडेंटिटी सही विस्तार प्रदान करती है।

फॉलो-अप 3: आप इसके बजाय आर्टिकुलेशन पॉइंट्स (Articulation Points) कैसे लौटाएंगे?

लो-लिंक डेटा पुन: प्रयोज्य है, लेकिन स्थिति किनारों से वर्टिकल (vertices) पर स्थानांतरित हो जाती है। एक गैर-रूट नोड u एक आर्टिकुलेशन पॉइंट होता है जब उसके पास low[v] >= tin[u] वाला एक DFS चाइल्ड v होता है। एक DFS रूट केवल तभी एक आर्टिकुलेशन पॉइंट होता है जब उसके पास कम से कम दो DFS-ट्री बच्चे हों। ध्यान दें कि समानता वर्टेक्स स्थिति से संबंधित है, जबकि ब्रिज डिटेक्शन सख्त > का उपयोग करता है।

फॉलो-अप 4: जब किनारे लगातार जोड़े जाते हैं तो क्या बदलता है?

यह एल्गोरिदम लीनियर समय में एक स्थिर स्नैपशॉट का उत्तर देता है। प्रत्येक इंसर्शन के बाद पुनर्गणना करने पर प्रति अपडेट O(n + m) खर्च होता है। केवल इंसर्शन वाला वर्कलोड एक विशेष ऑनलाइन डेटा संरचना के साथ ब्रिज की जानकारी बनाए रख सकता है; मनमाने ढंग से जोड़ने और हटाने के लिए अधिक सामान्य डायनेमिक-कनेक्टिविटी डिज़ाइन की आवश्यकता होती है। किसी एक का चयन करने से पहले अपडेट प्रकार, क्वेरी दर और निरंतरता आवश्यकता को स्पष्ट करें।

फॉलो-अप 5: रिपीटेड-सर्च बेसलाइन अभी भी बेहतर उत्तर कब है?

एक छोटे ग्राफ, एक संदिग्ध किनारे, या डायग्नोस्टिक कोड के लिए जहाँ लेटेंसी की तुलना में सरलता अधिक महत्वपूर्ण है, एक किनारे को छोड़ना और BFS चलाना छोटा और निरीक्षण करने में आसान है। एक किनारे के लिए इसकी O(n + m) लागत का उल्लेख करें और जब तक कार्य वास्तव में सभी ब्रिजेस या दोहराई गई प्रश्नों की मांग न करे, तब तक लो-लिंक स्टेट को पेश करने से बचें।