प्रश्न और परिदृश्य
ग्राफ़ में n वर्टिकल (vertices) और m निर्देशित किनारे (directed edges) हैं। वर्टिकल में कोई आउटगोइंग किनारा नहीं हो सकता है, किनारे दोहराए जा सकते हैं, और ग्राफ़ के कनेक्टेड होने की गारंटी नहीं है। एक स्ट्रॉन्गली कनेक्टेड कॉम्पोनेंट एक ऐसा सेट है जिसमें वर्टिकल का प्रत्येक युग्म एक-दूसरे तक पहुँच सकता है। सभी कॉम्पोनेंट्स को लौटाएं और बताएं कि उन्हें संकुचित (contracting) करने से एक निर्देशित अचक्रीय ग्राफ़ (directed acyclic graph / DAG) कैसे बनता है।
इंटरव्यूअर क्या टेस्ट कर रहा है
- क्या उम्मीदवार DFS इंडेक्स,
lowवैल्यूज़, स्टैक मेंबरशिप और कॉम्पोनेंट ID को सही ढंग से बनाए रख सकता है? - क्या वे
lowको अपडेट करते समय ट्री एज, बैक एज और पहले से पूर्ण हो चुके कॉम्पोनेंट के किनारों के बीच अंतर कर सकते हैं? - क्या वे डिस्कनेक्टेड ग्राफ़, सेल्फ़-लूप, समानांतर किनारों और रिकर्सन-डेप्थ के जोखिम को कवर करते हैं?
- क्या वे O(n+m) समय और O(n) सहायक स्पेस बता सकते हैं और इनवेरिएंट्स का परीक्षण कर सकते हैं?
शुरुआत में पूछे जाने वाले स्पष्टीकरण प्रश्न
पुष्टि करें कि क्या वर्टेक्स ID क्रमिक (contiguous) हैं, क्या समानांतर किनारों की अनुमति है, क्या कॉम्पोनेंट सदस्यों को सॉर्ट करने की आवश्यकता है, और क्या रनटाइम रिकर्सन की गहराई को सीमित करता है। ग्राफ़ के आकार, इंक्रीमेंटल-अपडेट की ज़रूरतों को स्पष्ट करें, और क्या केवल समान-कॉम्पोनेंट वाली क्वेरी की आवश्यकता है। बहुत गहरे ग्राफ़ के लिए, रिकर्सन और एक स्पष्ट स्टैक (explicit stack) के बीच ट्रेड-ऑफ़ बताएं।
30-सेकंड का उत्तर ढांचा
एक DFS चलाएं और प्रत्येक वर्टेक्स को एक बढ़ता हुआ इंडेक्स और बैक एज द्वारा पहुँच योग्य सबसे छोटा इंडेक्स असाइन करें, जिसे low कहा जाता है। प्रत्येक वर्टेक्स को पुश और मार्क करें, फिर पड़ोसियों का निरीक्षण करें: एक अनविज़िटेड पड़ोसी पर रिकर्स करें और उसके low का उपयोग करें; अभी भी स्टैक पर मौजूद पड़ोसी के लिए, उसके इंडेक्स का उपयोग करें। जब low वर्टेक्स के अपने इंडेक्स के बराबर होता है, तो यह एक कॉम्पोनेंट रूट होता है; उस वर्टेक्स तक पॉप करें। प्रत्येक वर्टेक्स और किनारे पर निरंतर कार्य होता है, इसलिए कॉम्प्लेक्सिटी O(n+m) है।
चरण-दर-चरण गहन विश्लेषण
- स्टेट इनिशियलाइज़ करें। प्रत्येक वर्टेक्स के लिए एक इंडेक्स,
low, स्टैक-मेंबरशिप फ़्लैग और कॉम्पोनेंट ID रखें। डिस्कनेक्टेड इनपुट को कवर करने के लिए प्रत्येक अनविज़िटेड वर्टेक्स से DFS शुरू करें। - अनविज़िटेड पड़ोसी को प्रोसेस करें। रिकर्स करें, फिर
low[u] = min(low[u], low[v])लागू करें। यह DFS सबट्री से स्टैक के पिछले वर्टेक्स तक के पाथ को रिकॉर्ड करता है। - स्टैक के पड़ोसी को प्रोसेस करें। यदि पड़ोसी अभी भी स्टैक पर है, तो
low[u]को पड़ोसी के इंडेक्स के साथ अपडेट करें। किसी अन्य कॉम्पोनेंट में पहले से पॉप किया गया वर्टेक्स इस बैकट्रैक में भाग नहीं ले सकता है। - रूट खोजें और पॉप करें। जब
low[u] == index[u]होता है, तो u रूट होता है। u के पॉप होने तक पॉप करें और मेंबरशिप फ़्लैग साफ़ करें; वे वर्टिकल एक स्ट्रॉन्गली कनेक्टेड कॉम्पोनेंट बनाते हैं। - सीमाओं (boundaries) को संभालें। एक सेल्फ़-लूप अभी भी एक सिंगलटन कॉम्पोनेंट उत्पन्न करता है; समानांतर किनारे समान न्यूनतम अपडेट को दोहराते हैं; एक पृथक (isolated) वर्टेक्स पुश किए जाने पर सिंगलटन बन जाता है।
- मान्य करें और संघनित (condense) करें। जाँचें कि प्रत्येक वर्टेक्स ठीक एक कॉम्पोनेंट से संबंधित है और कॉम्पोनेंट्स के बीच के किनारे एक DAG बनाते हैं। ट्रांज़िटिव क्लोज़र या Kosaraju के साथ रैंडम छोटे ग्राफ़ की तुलना करें, फिर बड़े ग्राफ़ पर कॉम्प्लेक्सिटी और स्टैक डेप्थ का परीक्षण करें।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं चार ऐरे बनाए रखूंगा: एक बढ़ता हुआ index, एक low बैक-लिंक वैल्यू, एक स्टैक-मेंबरशिप फ़्लैग और एक कॉम्पोनेंट ID। DFS प्रविष्टि पर, एक इंडेक्स असाइन करें और वर्टेक्स को पुश करें। एक अनविज़िटेड पड़ोसी के लिए, रिकर्स करें और इसके low वैल्यू को आगे बढ़ाएं (propagate); अभी भी स्टैक पर मौजूद पड़ोसी के लिए, केवल उस पड़ोसी के इंडेक्स को आगे बढ़ाएं। पूर्ण हो चुके कॉम्पोनेंट्स कभी भी अपडेट में भाग नहीं लेते हैं।
जब low[u] == index[u] होता है, तो u एक रूट होता है, इसलिए u तक पॉप करें और फ़्लैग साफ़ करें। प्रत्येक अनविज़िटेड वर्टेक्स से DFS शुरू करें, ताकि कनेक्टिविटी का अनुमान न लगाया जाए। प्रत्येक वर्टेक्स को एक बार पुश और पॉप किया जाता है और प्रत्येक किनारे का एक बार निरीक्षण किया जाता है, जिससे O(n+m) समय और O(n) सहायक स्पेस मिलता है। परीक्षणों में सेल्फ़-लूप, समानांतर किनारे, पृथक वर्टिकल, लंबी श्रृंखलाएं, कई चक्र और डिस्कनेक्टेड ग्राफ़, साथ ही कॉम्पोनेंट विभाजन और संघनन DAG शामिल हैं।
सामान्य गलतियाँ
- प्रत्येक विज़िट किए गए पड़ोसी के low वैल्यू से अपडेट करना और गलती से पूर्ण हो चुके कॉम्पोनेंट में बैकट्रैक कर जाना।
- कॉम्पोनेंट को पॉप करने के बाद स्टैक मेंबरशिप को साफ़ करना भूल जाना, ताकि बाद के किनारे पुराने वर्टिकल को वर्तमान पूर्वज (ancestor) के रूप में मानें।
- केवल एक वर्टेक्स से DFS शुरू करना और डिस्कनेक्टेड इनपुट में कॉम्पोनेंट्स को छोड़ देना।
lowके वर्तमान इंडेक्स के बराबर होने की व्याख्या "कोई किनारा नहीं" के रूप में करना, बजाय इसके कि "यह वर्टेक्स कॉम्पोनेंट रूट है।"- स्पष्ट स्टैक, चंकिंग या रनटाइम कॉन्फ़िगरेशन पर चर्चा किए बिना भाषा की स्टैक सीमा को पार कर जाना।
फॉलो-अप प्रश्न और उत्तर
पॉप किया गया वर्टेक्स low को अपडेट क्यों नहीं कर सकता है?
यह पहले से ही एक पूर्ण कॉम्पोनेंट से संबंधित है और वर्तमान DFS पाथ पर अब बैकट्रैक पूर्वज नहीं है। इसके low वैल्यू का उपयोग करने से कॉम्पोनेंट की सीमाएं पार हो जाएंगी और मैक्सिमैलिटी नष्ट हो जाएगी।
आप कैसे साबित करते हैं कि प्रत्येक कॉम्पोनेंट ठीक एक बार पॉप होता है?
प्रत्येक वर्टेक्स को एक बार पुश किया जाता है, और केवल एक रूट ही पॉपिंग को ट्रिगर कर सकता है। पॉप करने के बाद, इसका स्टैक फ़्लैग साफ़ कर दिया जाता है और DFS इसे फिर कभी पुश नहीं करता है, इसलिए प्रत्येक वर्टेक्स ठीक एक कॉम्पोनेंट से संबंधित होता है।
आप Tarjan बनाम Kosaraju को कैसे चुनते हैं?
Tarjan एक DFS का उपयोग करता है और कोई ट्रांसपोज़्ड ग्राफ़ नहीं रखता, जिससे ट्रैवर्सल और स्टोरेज कम हो सकता है। Kosaraju दो DFS पास का उपयोग करता है और चरणों को स्पष्ट रूप से अलग करता है। दोनों O(n+m) हैं; स्टैक सीमाओं, पठनीयता और मौजूदा ग्राफ़ प्रतिनिधित्व के आधार पर चुनें।