हेलो एवरीवन वेलकम टू माय चैनल कोट सरी विथ माइक तो आज अपने ग्राफ्स के प्लेलिस्ट का वीडियो नंबर 54 करने जा रहे हैं काफी अच्छा प्रॉब्लम है इसको हार्ड मतलब यह जिन लोगों ने पढ़ रखा हो ऑलरेडी ग्राफ से रिलेटेड एल्गोरिथम्स उनके लिए मीडियम मार्क क्वेश्चन किया जा सकता है ठीक है बट यह क्वेश्चन टू बी नेस्ट बहुत ही अच्छा है काफी चीज़ें इसमें आपकी चेक हो सकती हैं इसलिए इंटरव्यू के लिए काफी आइडियल प्रॉब्लम है यह है ना हाई लेवल इंटरव्यू के लिए लीड कोड नंबर 20457 मिनिमम टाइम टू रीच अ डेस्टिनेशन अ सिटी इज़ रिप्रेजेंटेड बाय अ बाय डायरेक्शनल कनेक्टेड ग्राफ क्लियर कट दे दिया कि ग्राफ का प्रॉब्लम है जिसमें n वर्टिसेज हैं और वर्टिसेज का नंबरिंग वन से लेकर n तक कर रखा है द एजेस इन द ग्राफ आर रिप्रेजेंटेड एज़ अ 2d मैट्रिक्स ठीक है यह देखो एजेस दे रखा होगा और यह बाय डायरेक्शनल एज होगा बिटवीन u एंड v एवरी वर्टेक्स पेयर इज़ कनेक्टेड बाय एट मोस्ट वन एज है ना ज्यादा से ज्यादा एक ही एज होगा कोई भी दो वर्टेक्स के बीच में उससे ज्यादा एज नहीं हो सकता ठीक है एंड नो वर्टेक्स हैन एज टू इट सेल्फ इसका मतलब क्या हुआ कि साइकल नहीं होगा मतलब कोई भी वर्टेक्स है कोई भी ऐसा एज नहीं निकलेगा जो वापस इसी पर आगे निपट जाए ठीक है तो साइकल नहीं होगा ओके द टाइम टेकन टू ट्रैवर्स एनी एस टाइम मिनट्स मतलब को किसी भी एज को ट्रैवर्स करने में इतना मिनट लगेगा वह पहले ही दे दिया है आपको ठीक है तो यहां पर कुछ चीजें पता चल चुकी है हमें कि भाई बाय डायरेक्शनल एज है और वर्टेक्स है कोई भी साइकल नहीं है ठीक है और हर ज को ट्रैवर्स करने में टा टाइम मिनट्स लग रहा है ईच वर्टेक्स हैज अ ट्रैफिक सिग्नल चच चेंजेज इट्स कलर फ्रॉम ग्रीन टू रेड ये सबसे इंपॉर्टेंट पार्ट है इस प्रॉब्लम का और चैलेंजिंग पार्ट यही है वो भी आसान हो जाएगा टेंशन नहीं है देखो ध्यान देना हर वर्टेक्स में एक ट्रैफिक सिग्नल रगा है जो कि ग्रीन होता है रेड होता है फिर ग्रीन होता है फिर रेड होता है फिर ग्रीन होता है फिर रेड होता है वाइस वर्सा वो होता रहता है फ्लिकर करते रहता है ठीक है अल्टरनेट होता रहेगा ग्रीन रेड ग्रीन रेड एंड सो ऑन लेकिन और वो जो अल्टरनेट होता है वो हर चेंज मिनट्स के बाद होता रहेगा मान लेते हैं चेंज मिनट की वैल्यू फाइव है तो अभी ट्रैफिक सिग्नल की वैल्यू ग्रीन है तो 5 मिनट के लिए यह ग्रीन रहेगा उसके बाद नेक्स्ट 5 मिनट के लिए वो रेड रहेगा उसके बाद नेक्स्ट 5 मिनट के लिए वो ग्रीन रहेगा एंड सो ऑन ठीक है ऑल द सिग्नल्स चेंज एट द सेम टाइम और हर वर्टेक्स जितने भी वर्टेक्स है ना हर में यह वाला सिग्नल लगा होगा और सभी का सिग्नल सेम टाइम पर चेंज होता है अगर यह रेड है तो सभी लोग रेड होंगे उस वक्त अगर यह ग्रीन है तो सभी लोग ग्रीन होंगे उस वक्त यहां तक क्लियर है ओके यू कैन एंटर अ वर्टेक्स एट एनी टाइम ठीक है आप किसी वर्टेक्स में किसी भी टाइम घुस सकते हो बट कैन लीव अ वर्टेक्स ओनली व्हेन द सिग्नल इज ग्रीन है ना बट उस वर्टेक्स से आप तभी निकल सकते हो जब आपका सिग्नल वहां पर ग्रीन होगा यू कैन नॉट वेट एट अ वर्टेक्स इ द सिग्नल इज ग्रीन और अगर ग्रीन हो गया तो आप वेट नहीं कर सकते आपको वहां से निकलना ही पड़ेगा ठीक है द सेकंड मिनिमम वैल्यू इज डिफाइंड एज द स्मालेस्ट वैल्यू स्ट्रिक्टली लार्जेस्ट देन द मिनिमम वैल्यू हां सेकंड मिनिमम वैल्यू का मतलब क्या हुआ जो सबसे छोटा वैल्यू है वो तो मिनिमम हो गया उसके जस्ट बाद बड़ा जो भी होगा इक्वल भी नहीं है एकदम स्ट्रिक्टली ला लार्जर चाहिए जैसे मान लेते हैं ये अरे देख लो इसमें मिनिमम वैल्यू कौन है टू है इसके जस्ट मिनिमम कौन है इसके जस्ट थोड़ा सा बड़ा कौन है थ्री है थ्री इज द सेकंड मिनिमम और ये देखो ये इंपॉर्टेंट एग्जांपल है इसमें देखो 2 2 4 है ना इसमें मिनिमम कौन है बताओ तो इसमें मिनिमम टू है और सेकंड मिनिमम टू नहीं हो सकता सेम वैल्यू हो ही नहीं सकता इस टू से जस्ट बड़ा जो वैल्यू होगा वो सेकंड मिनिमम होगा तो इस केस में देखो सेकंड मिनिमम फोर है तो इस चीज का भी हमें ध्यान देना है ये भी थोड़ा सा ये माइन छोटी सी चीज है जो हमें ध्यान देना है सॉल्व करते वक्त तो आपको क्या-क्या दे रखा होगा n दे रखा होगा कि इतने वर्टिस है एजेस दे रखा होगा टाइम दे रखा है कि भाई हर एज को ट्रैवर्स करने में कितना टाइम लगता है और चेंज दे रखा है कि हर इतने चेंज टाइम के बाद सिग्नल अल्टरनेट होगा रिटर्न द सेकंड मिनिमम टाइम इट विल टेक टू गो फ्रॉम व वर्टेक्स वन अच्छा सोर्स दे रखा है ऑलरेडी आपका सोर्स दे रखा है और वर्टेक्स एंड डेस्टिनेशन भी दे रखा है ये आपका डेस्टिनेशन है यहां तक क्लियर है ठीक है यू कैन गो थ्रू एनी वर्टेक्स एनी नंबर ऑफ टाइम्स इंक्लूडिंग वन एंड एन यू कैन एज्यूम दैट व्हेन द जर्नी स्टार्टस ऑल सिग्नल्स हैव जस्ट टर्न ग्रीन ठीक है मतलब जब आप वन पर खड़े हो ना जब आप जर्नी स्टार्ट कर रहे हो तो अज्यू करके चल सकते हैं कि वहां पर अभी ग्रीन है तो आप निकल सकते हो उसी वक्त वहां से ठीक है ओके तो देखते हैं ये एग्जांपल है इसका आउटपुट 13 क्यों बता रहा है वो भी देख लेते हैं अ एज के हिसाब से मैंने ग्राफ बना दिया है हर एज को ट्रैवर्स करने में 3 सेकंड लगता है या 3 मिनट जो भी है और चेंज क्या है अल्टरनेट होता है सिग्नल रेड टू ग्रीन या ग्रीन टू रेड एट एवरी फाइव सेकंड्स ओके ठीक है एवरी 5 सेकंड्स या 5 मिनट जो भी यूनिट आपको रखना है अब देखो यहां पर आंसर 13 क्यों है वो बताता हूं अभी देखो अभी आप स्टार्टिंग में यहां खड़े हुए आपका सोर्स है राइट तो वन एक पाथ तो आपको और आपको जाना है यह फाइव के पास फाइव आपका डेस्टिनेशन है तो अभी टाइम जीरो सेकंड्स हो रहा है तो अभी याद करो प्रॉब्लम में दे रखा है कि अज्यू करो कि जीरो सेकंड में ग्रीन सिग्नल हो रखा है तो ओबवियस बात है नेक्स्ट फ सेकंड्स के लिए अभी आपका सिग्नल ग्रीन होने वाला है राइट तो मैं एक नंबर लाइन बना देता हूं यहां पर टाइम का कि भाई 5 सेकंड 10 सेकंड 15 सेकंड 20 सेकंड 25 सेकंड एंड सो ऑन तो अभी ज जीरो सेकंड प आपने स्टार्ट किया है और नेक्स्ट फ सेकंड्स तक वो ग्रीन रहने वाला है उसके बाद रेड रहेगा उसके बाद फिर से ग्रीन रहेगा उसके बाद रेड रहेगा उसके बाद फिर से ग्रीन रहेगा ठीक है तो अभी आप यहां पर खड़े हो तो आपने देखा अच्छा ग्रीन है तो आपको निकालना तो पड़ेगा ही पड़ेगा तो आप वन से मान लेते हैं आप फोर गए कितना टाइम लगता है याद करो एज को ट्रैवर्स करने में तीन टाइम लगता है तो मैं टाइम यहां पर कैलकुलेट करता रहता हूं कि आप वन से फोर गए और आपको तीन मिनट लगा या न सेकंड लगा ठीक है अभी देखो टाइम इक्वल टू 3 सेकंड मतलब अभी आप यहीं पर कहीं पर हो है ना इधर कहीं खड़े हो तो अभी भी ग्रीन में ही हो आप ना तो अभी भी आप झट से तुरंत निकल सकते हो और आपको निकलना ही पड़ेगा है ना तो यहां से ज से आप निकले तो आप फाइव के पास पहुंच गए तो इस एज को ट्रव्स करने में फिर से आपके कितना लगा होगा तीन लगा होगा तो देख रहे मिनिमम टाइम दिख गया मुझे फ में पहुंचने का जो कि है 6 सेकंड या 6 मिनट जो भी बोललो ठीक है छ लग रहा है सोर्स नेशन जाने में लेकिन यह मिनिमम है आपका है ना ओके हमें निकालना है सेकंड मिनिमम तो देखते हैं सेकंड मिनिमम हमारा क्या होगा मैं इसको दूसरे कलर से रिप्रेजेंट करता हूं मान के चलते हैं आप वन से थ्री गए ठीक है अभी आप ग्रीन पे ही हो ओबवियस सी बात है क्योंकि जस्ट आपने स्टार्ट किया है वन से थ्री गए आपको ्र मिनट्स लगा यहां पर ठीक है तो ये टाइम टू मान लेते हैं इसको ये तो टाइम सेकंड मिनिमम 3 सेकंड लगा इस एज को ट्रैवर्स करने में आप वन से थ्री जा चुके हो अभी भी तीन ही सेकंड गुजर है मतलब आप यहां पर कहीं खड़े हो मतलब अभी आप ग्रीन वाले सेक्शन में हो 5 सेकंड अभी गुजरा नहीं है ठीक है तो अभी आप झट से फिर यहां चले जाओगे फोर पर चले जाओगे तो फिर से न सेकंड लगाओ क्योंकि एज को ट्रैवर्स करने में 3 सेकंड लगता है तो अभी छ हो चुका है ठीक है अब देखिए आपको डेस्टिनेशन प पहुंचना है राइट अभी तक आप पहुंचे नहीं हो डेस्टिनेशन में तो आप फोर से जब फव जाओगे तो एक प्रॉब्लम है यहां पर अभी देखो 6 सेकंड हो चुका है ध्यान देना मैं क्या बोल रहा हूं अभी आप चार पर पहुंचे हुए हो और कितना समय पास हो चुका है 6 सेकंड पास हो चुका है मतलब अगर आप इस नंबर ला ला में देखो तो पांच आपने कवर कर लिया और अभी आप छठे सेकंड में हो ये सिक्स है मान लेते हैं तो देखो तो कौन से रीजन में हो अभी आप रेड रीजन में हो मतलब अभी आप नहीं निकल सकते यहां से यहां से तो अब नेक्स्ट कब निकल पाओगे जब 10 सेकंड होगा ऑब्स होता तभी ना फिर ग्रीन स्टार्ट होगा जब 10 सेकंड होगा तभी ग्रीन स्टार्ट होगा तब आप यहां से निकल पाओगे ठीक है तो ओबवियस सी बात है आप थोड़ा देर यहां पर और वेट करोगे जब तक ये 10 सेकंड ना गुजर जाए तो 10 सेकंड गुजर गया ये भी गुजर गया आपने आपको जितना वेट करना था आपने वेट कर लिया ठीक है अब जब 10 सेकंड गुजर गया तब आप यह ट्रैवर्स मार सकते हो अब आप चार से पांच गए ठीक है तो एज को ट्रैवर्स करने में 3 सेकंड एक्स्ट्रा लगता ही लगता है तो याद करो 10 सेकंड गुजर चुका था और अभी आपने जस्ट इस एज को ट्रैवर्स किया है 3 सेकंड में तो कितना हो गया 13 सेकंड हो गया ठीक है अब आप डेस्टिनेशन में पहुंच गए हो 13 सेकंड में तो देखो ये मेरा मिनिमम टाइम था टू रीच द डेस्टिनेशन फ्रॉम द सोर्स और ये मेरा सेकंड मिनिमम टाइम है टू रीच द डेस्टिनेशन फ्रॉम द सोर्स ठीक है तो आंसर हमारा इसीलिए 13 है यहां पर ओके यहां तक क्लियर है ठीक है अब हमारा देखते हैं क्या हमारा थॉट प्रोसेस होना चाहिए किस तरह हमें इसको सॉल्व करना चाहिए अब देखो ध्यान दो यहां पर हमें यहां पर क्या निकालना है वन से ये वन मेरा सोर्स है फव मिनट डेस्टिनेशन है हमें मिनिमम टाइम निकालना है राइट मतलब शॉर्टेस्ट पाथ निकालना है वन से लेकर फाइव तक तो एक सिंगल सोर्स दे रखा है और एक सिंगल डेस्टिनेशन दे दे रखा है हमें शॉर्टेस्ट पाथ निकालना है और प्रॉब्लम में दे रखा है कि कोई साइकल नहीं होगा हमारे पास ठीक है बट हां ये अ अनडायरेक्टेड ग्राफ है राइट तो आपको याद करो एक सिंगल सोर्स डेस्टिनेशन सिंगल सोर्स से अगर शॉर्टेस्ट पाथ निकालना होता था सारे नोट्स का तो हम क्या यूज करते थे डाइक्स एल्गोरिथम यूज करते थे है ना और भी कुछ एल्गोरिथम है बट हम डाइक्स एल्गोरिथम मेनली यही यूज करते थे सिंगल सोर्स शॉर्टेस्ट पाथ क्योंकि हमारे पास सिंगल सोर्स दे रखा है मुझे इससे इस डेस्टिनेशन का शॉर्टेस्ट पाथ चाहिए ठीक है ठीक है डारा मेरे मन में आ तो रहा है ब डारा में याद है क्या बोला था कि डैग में अप्लाई करते हैं डारा को डायरेक्टेड एसाइक्लिक ग्राफ में अप्लाई करते हैं डाा को ठीक है बट आई नो यह अनडायरेक्टेड है बट इसको अनडायरेक्टेड को आप ऐसे ही मान सकते हो ना कि ये और यह यह भी तो डायरेक्टेड हो गया अनडायरेक्टेड का मतलब क्या हो कि दोनों तरफ का ये एरो है मतलब यहां से यहां जा सकता हो और यहां से यहां जा सकते हो ठीक है तो देखते हैं कि अन डाइक्स एल्गोरिथम से हम इसको बना सकते हैं कि नहीं तो आपको डाइक्स एल्गोरिथम का थोड़ा सा अगर मैं रिवीजन कर रहा हूं तो आपको याद होगा कि सिंगल सोर्स शॉर्टेस्ट पाथ होता था उसमें हम एक रिजल्ट वेक्टर बनाते थे जिसमें फ्रॉम अ गिवन सोर्स हमारा सोर्स यहां पर s है इस सोर्स से बाकी सारे नोट्स का डिस्टेंस हम लोग इस रिजल्ट में स्टोर कर लेते थे स्टार्टिंग में इसको इंफिनिटी रखते थे है ना और उसके बाद नोड नंबर 1 2 3 4 5 सस नोड है नहीं बट स्टिल लिख देते हैं अभी के लिए ठीक है सारे नोट से इसकी दूरी निकाल ते थे तो सोर्स का सोर्स अभी वन है ना तो वन का वन से दूरी कितना होगा ओबवियस है जीरो होगा यहां तो जीरो लिख देते थे उसके बाद डायस एल्गोरिथम लगाते थे और बाकी सबको फिल कर देते थे राइट ठीक है अब मुझे बस जानना है कि इस सोर्स का इस फाइव से कितना मिनिमम दूरी है तो इस फ फिफ्थ इंडेक्स में जाएंगे आराम से हमें आंसर मिल जाएगा ठीक है बट यहां पर प्रॉब्लम क्या है कि हमें सेकंड मिनिमम डिस्टेंस चाहिए सेकंड मिनिमम तो देखो अब एक चीज ध्यान दो यह तो मेरा रिजल्ट वेक्टर होता था और यह मेरा सोर्स से शॉर्टेस्ट डिस्टेंस यानी कि मिनिमम डिस्टेंस शोर करता था तो इसको अगर मैं यहां पर स्टोर कर लू इसका नाम दे देता हूं मिनिमम डिस्टेंस स्टोर करता था ड गदम के थ्रू तो एक काम करते हैं ना सिंस ये वाला अरे मेरा मिनिमम डिस्टेंस स्टोर कर रहा है तो इसको मिनिमम डिस्टेंस वन नाम दे देते हैं और एक और अरे ले लेंगे सेम और उसका नाम मिनिमम डिस्टेंस टू रख देंगे और उसमें क्या करेंगे मिनिमम डिस्टेंस अ सेकंड मिनिमम डिस्टेंस इसमें स्टोर करेंगे ठीक है तो मैं एग्जांपल के तौर पे आपको बता देता हूं जैसे मान के चलते हैं पहले तो इसका नंबरिंग कर देते हैं 1 2 3 4 5 है मान लेते और स्टार्टिंग में इसमें भी इंफिनिटी है सारा का सारा ठीक है अब एक चीज ध्यान दो यहां पर यह जो मिन d2 है ना इसमें मैं सेकंड मिनिमम डिस्टेंस स्टोर करूंगा और प्रॉब्लम में याद है क्या बोला था कि जो सेकंड मिनिमम डिस्टेंस है वो मिनिमम के बराबर नहीं हो सकता है ना तो यहां पर मुझे ध्यान देना पड़ेगा कि यहां पर मैं जीरो यहां नहीं डाल सकता भले मेरा सोर्स वन ही है वन से वन का मिनिमम डिस्टेंस जीरो है बट सेकंड मिनिमम डिस्टेंस अभी तक मुझे नहीं पता इसलिए मैंने यहां पर भी अभी इंफिनिटी लिख रखा है ठीक है तो हम लोग पता है कैसे पॉपलेट करेंगे देखो ध्यान दो मान के चलते हैं आपने डायस लगाया आप वन से थ्री पहुंचने का मान के चलते हैं न से थ पहुंचने का आपने मिनिमम डिस्टेंस 10 निकाल लिया मान के चलते हैं ठीक है तो आपने देखा कि अच्छा मिनिमम डिस्टेंस अभी तक ्र में पहुंचने का मैंने नहीं निकाला है क्योंकि देखो इसकी वैल्यू इनफिनिटी है अभी तक नहीं निकाला होगा तो कोई बात नहीं यहां पर मैं 10 डाल देता हूं ठीक है ओके अब मान के चलते डायरेक्शन आगे और रन किया आपने और यहां पर पहुंचने का मिनिमम डिस्टेंस आपको ्र मिल चुका है एक बेटर डिस्टेंस मिल चुका है तो पहले तो आपने देखा कि अच्छा मिनी d1 में यहां पर डिस्टेंस स्टोर्ड है क्या थ्री के लिए पहुंचने के लिए य स्टोर्ड है 10 है बट वो बड़ा है मेरे करंट वैल्यू से अभी मुझे और बेटर वैल्यू मिल चुका है 3 मिल चुका है ठीक है तो मैं क्या करूंगा ना इस 10 को ओबवियस ये 10 मेरा सेकंड मिनिमम बन जाएगा तो मैं 10 को यहां पर डाल दूंगा और ्र को यहां डाल दूंगा क्योंकि मुझे थ्री अभी बेटर डिस्टेंस या बेटर टाइम मिला है पहुंचने का इस नोड 3 में पहुंचने का ठीक है तो अपडेट कर देंगे ये वही सिंपल सा चीज है याद करो जब हम मिनिमम और सेकंड मिनिमम निकालते थे तो कैसे करते थे मान लेते हैं अभी मुझे का वैल्यू इनफिनिटी है अभी मुझे 10 मिला है वैल्यू तो मिनिमम मेरा 10 हो जाएगा सेकंड में इंफिनिटी है अभी मुझे पांच मिला तो मिनिमम पांच हो जाएगा और जो सेकंड मिनिमम है जो पहले मिनिमम की वैल्यू थी वो यहां सेट हो जाएगा तो नॉर्मल सा चीज वही कर रहा हूं मैं बस यहां पर तो हर नोड का सोर्स से मिनिमम डिस्टेंस भी मैं निकाल लूंगा और सेकंड मिनि डिस्टेंस भी मैं स्टोर कर लूंगा एक अरे में डिफरेंट अरे में ठीक है यहां तक क्लियर है तो मेरा लॉजिक कुछ ऐसे बनने वाला है ओके अब आगे हम लोग कैसे प्रोसीड करेंगे वो देखते हैं और क्या-क्या चीजों का हमें ध्यान देना है वो देखते हैं एक और छोटे चीज पे यहां पर ध्यान दो देखो जब पहली बार आपने मिन d1 को अपडेट किया था तो ओबवियस सी बात है वो मिनिमम वैल्यू मुझे मिला था तब के टाइम पे याद करो अब मान लेते हैं अभी इंफिनिटी है जब पहली बार आपने इस थ्री के डिस्टेंस को अपडेट किया था तो ओबवियस सी बात है एक छोटा वैल्यू मिला होगा तो आपने 10 डाल दिया ठीक है तो ओबवियस सी बात है मतलब थ्री को अभी आपने एक बार विजिट किया है राइट एक बार विजिट किया है अभी आपने थ्री को क्योंकि पहली बार विजिट किया है तो अ बात है मिनिमम डिस्टेंस यहां आपने अपडेट कर दिया जब फ्यूचर में दोबारा आप इस थी पर आए मान के चलते आपको एक और बेटर डिस्टेंस मिल गया थ ठीक है तो अ आपने क्या किया यहां पर ्र डाल दिया और यहां पर 10 डाल दिया तो इस थ्री को आपने कितनी बार विजिट कर लिया एक बार और विजिट कर लिया ठीक है अब मुझे एक बात बताओ डाइक्स एल्गोरिथम तो यहां मिनिमम डिस्टेंस निकाल देता है राइट तो इस मुझे किसी भी नोट को दो बार से ज्यादा विजिट करने की दूरी जरूरत है क्या नहीं जरूरत है क्योंकि दो बार में क्या होगा मुझे मिनिमम और सेकंड मिनिमम मिल जाएगा तो किसी नोड को मैं दो बार से ज्यादा विजिट नहीं करूंगा तो इस चीज का हम ध्यान रख सकते हैं ठीक है किसी भी नोड को हम दो बार से ज्यादा विजिट नहीं करेंगे ओके अब देखो ध्यान दो यहां पर यह तो हमने समझ में आ गया कि हां भाई नॉर्मल सा डारा लगाएंगे और यह अपडेट करते चलेंगे और ध्यान रख लेंगे कि यहां दो बार अगर हम किसी नोट को विजिट कर चुके हैं ठीक है और जैसे मान लेते हैं फव है इसको मैंने दो बार विजिट कर लिया है तो ओबवियस बात है इसका सेकंड मिनिमम वैल्यू निकल चुका होगा राइट दो बार विजिट किया मतलब दो पहली बार में में ये अपडेट किया होगा दूसरी बार में फिर यह वाला अपडेट कर दिया होगा दोनों अपडेट हो गए होंगे ठीक है मतलब इस फाइव नोट का डेस्टिनेशन नोट को अगर मैंने दो बार विजिट कर लिया है ठीक है तो मतलब हमारा आंसर आ चुका होगा ठीक है और हम यहां से इसको रिटर्न कर देंगे कि कितना टाइम मेरा लगा होगा ओके अब देखो बस लास्ट चीज हमें देखना है जो कि इस प्रॉब्लम को कॉम्प्लेक्शन में कुछ और कॉम्प्लेक्टेड सेम कोड होगा डायरा का बट एक दो चीज का जो ध्यान देना है वो अभी मैं आपको बता देता हूं जो सबसे कॉम्प्लेक्शन का वो है कि भाई यह हर दो मतलब हर चेंज टाइम के बाद सिग्नल चेंज होता है और आप किसी भी नोड से किसी भी तभी निकल सकते हो आप किसी भी नोड से तभी निकल सकते हो जब वह ग्रीन सिग्नल पर हो ठीक है तो अब देखते हैं जैसे मान लो यहां पर याद है मैंने आपको क्या बोला था इस केस में कि जब मैं फोर पर पहुंचा ठीक है तो मैंने देखा कि मेरा टाइम अभी 6 सेकंड हो चुका है राइट अभी टोटल टाइम पास मेरा 6 सेकंड हो चुका क्योंकि याद करो 3 सेकंड प यहां पर आए थे 3 सेकंड प यहां पर आए थे क्योंकि अभी तक ग्रीन सिग्नल चल रहा था बट जब मैं फोर पर पहुंचा मैंने देखा कि अच्छा छ सेकंड पास हो चुके हैं ठीक है और मैं अभी रेड वाले पोर्शन में हूं तो जितने सेकंड पास हो चुके हैं उसके हिसाब से आप पता तो जरूर कर सकते हो कि अभी रेड चल रहा होगा या ग्रीन चल रहा होगा बहुत आसान है ठीक है वो भी मैं अभी आपको दिखा देता हूं जैसे मान लो मैं अभी यहां पर अपने क्या दिखाया मैंने आपको कि भाई एक नोड था फोर ठीक है और मैं इस नोड पर पहुंचा जब पहुंचा तो टोटल टाइम पास कितना हो चुका था टाइम पास कितना हो चुका था छ हो चुका था राइट और कितना सेकंड दे रखा था कि कितने सेकंड के बाद सिग्नल चेंज होता है आई थिंक सॉरी चेंज वेरिएबल था ना यहां मैं लिख देता हूं कि हर फ सेकंड्स के बाद सिग्नल चेंज होता अल्टरनेट होता है ठीक है ओके तो अब देखो ध्यान दो मैंने आपको क्या बताया कि भाई इस फोर नोड पर मैं पहुंचा तो जब फोर पर मैं पहुंचा तो इतना टाइम पास हो चुका था राइट ठीक है अब मुझे यह पता करना है कि अभी क्या मैं ग्रीन में ह हूं या फिर मैं रेड में हूं तो ग्रीन कब होगा मतलब दोबारा मैं कब यहां से निकल सकता हूं ठीक है तो पहले तो नंबर लाइन में आपको बना बना के दिखाता हूं ताकि आसानी हो समझने में पांच चेंज हमारा पाच पाच मिनट का है ना पाच पाच सेकंड का जो भी है तो पाच पाच का इंटरवल मैंने बना दिया 20 25 अब देखो ध्यान देना अभी करेंटली आप यहां पर हो मतलब सॉरी 5 सेकंड जब गुजर गया तो यहां पर ओबवियस है इस वक्त ग्रीन रहा होगा ठीक है अभी आप देखो टाइम पास्ड छ है ना मतलब आप यहां पर कहीं पर हो मतलब आप इस रेड वाले रीजन में हो ठीक है अब देखो ध्यान देना कि भाई अगर जैसे टोटल टाइम पास कितना है छ है ना इतना टाइम पास हो चुका है और हर कितने इंटरवल में हर कितने सेकंड के बाद चेंज होता है सिग्नल हर 5 सेकंड के बाद तो इसको चेंज से डिवाइड कर दिया जाए तो मैं यह पता कर सकता हूं कि कितनी बार अल्टरनेट हुआ है ठीक है तो 6 बाय चेंज यानी कि 6/5 कितना हो जाएगा 5 1 पॉइंट समथिंग होगा राइट ठीक है तो 1 पॉइंट समथिंग का मतलब क्या हुआ कि वन एक बार सिग्नल चेंज हुआ होगा मतलब एक इंटरवल पास हो चुका है 1 पॉइंट समथिंग मतलब एक इंटरवल पास हो चुका है उसके बाद मैं कहीं बीच पर खड़ा हूं ओबवियस से बात है ये सिक्स है तो देखो यही मैं कहीं बीच प खड़ा हूं ठीक है ओबवियस ी बात है और ये नेक्स्ट टाइम ये ग्रीन कब हो जाएगा जब मैं एगजैक्टली 10 नेक्स्ट मल्टीपल पर फ के नेक्स्ट मल्टीपल पर आ जाऊगा यहां पर आ जाऊगा ठीक है और तब टाइम क्या हो रखा होगा तब टाइम पास 10 हो रखा होगा जब आप यहां पर आ जाओगे तो ठीक है तो यह भी आप आराम से निकाल सकते हो देखो अभी तक कितना मल्टीपल फ का क्रॉस हो चुका बस एक मल्टीपल क्रॉस हुआ था ना फ का पास हुआ था न पॉइंट समथिंग है ठीक है तो आप ऐसा कर सकते हो कि 6 बाय चेंज का जो भी वैल्यू है उसका इंटी जर पार्ट ले लो ठीक है तो 6 बा चेंज करोगे तो वन आ जाएगा इंटी जर पार्ट बोल रहा हूं ठीक है उसमें बस + 1 कर दो ठीक है और चेंज से मल्टीप्लाई कर दो कितना हो जाएगा 10 हो जाएगा देखो ऑब्स बता आसानी से निकाल सकते हो वन वन पॉइंट था ना वन पॉइंट का मतलब क्या हुआ कि एक इंटरवल पास हो चुका है पॉइंट मतलब आप कहीं बीच में यहां पर फंसे हुए हो ठीक है तो मैंने इंटी जर वाला पार्ट ले लिया कि इतनी बार पांच हो चुका है 1 पॉइंट समथिंग है तो वन बार पा तो गुजर चुका है यह रहा वन टाइम पाच तो गुजर चुका है अब आप बीच में कहीं पर हो तो ठीक है तो तो बीच में जब कभी होगा तो नेक्स्ट कब इंटरवल चेंज होगा जब आप जस्ट नेक्स्ट वाले फाइव के इंटरवल पर आओगे इसलिए मैंने क्या किया एक बार फाइव का इंटरवल हो चुका था मैंने बस प्लस व कर दिया कि अब नेक्स्ट इंटरवल यहां पर खत्म होगा 10 पे तो 1 + 1 कर दिया और कितना इंटरवल इंटरवल का टाइम कितना था चेंज के बरा चेंज था ना चेंज की वैल्यू क्या फाइव दे रखी थी तो 5 * 10 कर दो तो 10 आ गया ठीक है यहां तक क्लियर है ठीक है कि नेक्स्ट टाइम आप 10 पे फ्री हो पाओगे ओके ठीक है तो अब एक चीज ध्यान दो कैसे मैंने इसको निकाला आराम से मैं फिर से बता देता हूं पहले तो मैंने फैक्टर निकाल लिया डिवाइड करने पर कितना फैक्टर आया मतलब टोटल टाइम पास्ड टोटल टाइम पास्ड डिवाइडेड बाय जो भी मेरा चेंज का वैल्यू है ठीक है तो इंटी जर वैल्यू मुझे ये दे देगा जैसे 1.4 या कुछ रहा होगा तो मुझे इंटी जर वैल्यू दे देगा इंटी जर वैल्यू से मुझे यह पता चल जाएगा कि कितना बार यह जो इंटरवल है वो पास हो चुका है ग्रीन रेड ग्रीन कितनी बार पास हो चुका है ठीक है अब देखो ध्यान दो यहां पर वैल्यू वन है मतलब क्या हुआ कि एक बार मेरा फाइव वाला इंटरवल क्रॉस हो चुका है एक बार बस एक ही बार हुआ है ठीक है तो एक बार मतलब पहला वाला ग्रीन पास हो चुका है और अभ ये पक्का आप रेड पे खड़े हो गया सही बात है आप रेड पे खड़े थे ये रहा सिक्स यहां पर है ठीक है ठीक है अब अब एक बात बताओ मान के चलते हैं कि ये इंटरवल जो डिवीजन की वैल्यू वो दो होती तो ये वन है ना मान लेते हैं दो होती इसका मतलब क्या हुआ कि दो बार ये वाला इंटरवल पास हो चुका है पहला इंटरवल में ग्रीन रहा होगा दूसरा इंटरवल भी पार हो चुका है जिसमें रेड रहा होगा ठीक है अब आप तीसरे इंटरवल प आ चुके होगे है ना अगर इसकी वैल्यू दो है तो ओके तो अब एक चीज ध्यान दो अगर मेरा वैल्यू ऑड है डिवीजन का जो भी वैल्यू आ रहा है टाइम पास ब अगर ये ऑड है तो पक्का आप रेड प खड़े हुए हो और अगर वो इवन है तो पक्का आप ग्रीन में हो ठीक है वो अभी आपको पता चल जाएगा टाइम पास्ड बाय चेंज की वैल्यू अगर वन है तो ओबवियस स बात है यह ग्रीन है अब पक्का आप रेड पर आ चुके होगे मतलब एक इंटरवल पास हो चुका है आप पक्का रेड पर आ चुके होगे आपको साफसाफ दिख रहा है है ना ऑड के केस में अगर इसकी वैल्यू दो होती डिवीजन की वैल्यू मतलब दो बार इंटरवल ये पास हो चुका है एक बार यह पास हुआ एक बार ये पास हुआ दो बार पास हो चुका मतलब आप ग्रीन वाले सेक्शन में आ चुके हो है ना ठीक है तो हम यहां पर एक चीज ये पता कर सकते हैं कि आप अभी निकल सकते हो कि नहीं निकल सकते हो ठीक है अगर आपकी वैल्यू मतलब अगर ये ऑड हुआ तो मतलब पक्का आप रेड में फंसे हुए हो आपको नेक्स्ट इस इंटरवल का खत्म होने का वेट करना पड़ेगा ठीक है और अगर आप ग्रीन पे हो तो आप कोई दिक्कत नहीं आप उसी वक्त निकल जाओ कोई दिक्कत कुछ वेट करने का जरूरत नहीं है ठीक है तो यहां पर अगर आप ध्यान दो अब इस वाले एग्जांपल पर आते हैं आपका वैल्यू क्या था अ टोटल टाइम पास सिक्स था ना तो 6 बाय चेंज आपने किया तो 1 पॉइंट समथिंग आया तो इसका इंटी जर पार्ट क्या हो जाएगा वन आ जाएगा ठीक है इसका इंटी जर पार्ट आ गया सि पा चज का इंटी जर पार्ट आ गया वन अब वन एक ऑड वैल्यू है ऑड वैल्यू का मतलब क्या हुआ कि आप पक्का रेड में खड़े हुए हो गए देख लो आपको साफ-साफ दिख भी रहा होगा वन का मतलब यही हुआ ना कि एक इन आपका का गुजर चुका है एक इंटरवल है ना और अब अभी आप पक्का यहां आ चुके होंगे तो वन एक ऑड वैल्यू है मतलब आप यहां पर रेड प खड़े हुए हो गए ठीक है ओके तो अगर यह ऑड है तो रेड पर है मतलब आपको अभी आपको और वेट करना पड़ेगा जब तक ये ग्रीन ना हो जाए तो नेक्स्ट ग्रीन कैसे निकालो अभी जस्ट आपको मैंने सिखाया कि जितना डिव का वैल्यू है मतलब ये वन है ना ठीक है जितना डि का वैल्यू उसमें एक प्लस वन और कर दो मतलब नेक्स्ट मल्टीपल वाले में आप पहुंच जाओगे इसको चेंज से मल्टीप्लाई कर दो तो 5 ट 10 हो जाएगा मतलब आप 10 सेकंड में आप नेक्स्ट फ्री हो ग ठीक है यहां तक क्लियर है ठीक है तो हमारा एम क्या रहेगा सबसे पहले मैं डिवीजन निकालू कि भाई डिवीजन का वैल्यू क्या है तो उससे मुझे यह पता चल जाएगा कितने बार टाइम पास्ड बाय चेंज है ना है ना तो मतलब कितनी बार ये चेंज इंटरवल हो चुका है एक इंटरवल हुआ है या दो हुआ है या तीन हुआ है एंड सो ऑन यह पता चल जाएगा अगर वो ऑड नंबर ऑफ टाइम्स हुआ है मतलब आप रेड वाले रीजन में खड़े हुए हो और अगर वो इवन नंबर ऑफ टाइम्स हुआ होगा तो मतलब आप ग्रीन में खड़े हुए हो आपको कोई दिक्कत नहीं अब आराम से आगे भाग जाओ ठीक है तो यहां पर देखो आप रेड वाले रीजन में खड़े हो क्योंकि ये ऑड है और अगर रेड वाले रीजन में खड़े हो यहां पर खड़े हो ना आप तो आपको इसको कंप्लीट होने का वेट करना पड़ेगा नेक्स्ट फिर आप कब फ्री हो पाओगे जब टाइम पास मेरा 10 हो जाएगा और वो 10 मेरा आसानी से निकाल सकते हो कैसे निकाल सकते हो डिवीजन जो भी वैल्यू आया है उसमें प्लस व कर देना प्लस व क्यों कर रहे है ताकि नेक्स्ट मल्टीपल मिल सके मुझे और इंटू चेंज कर देना चेंज की वैल्यू जो भी है इंटू इज इक्वल टू क्या हो जाएगा 10 आ जाएगा तो आपको नेक्स्ट किस वक्त आप फ्री हो जाओगे ग्रीन आ जाएगा आपके पास वो टाइम निकल कर आ जाएगा 10 तो यह तो 10 क्या निकल गया ये 10 ये निकल के आ गया कि इस वक्त ग्रीन हो चुका होगा अब आप यहां से मूव कर सकते हो अपने नेबर में जो भी आपका नेबर होगा नेबर आपका मान लेते हैं तो उस नेबर में मूव करने के लिए आपको याद करो कितना लगता था जो भी इसका दे रखा था टाइम दे रखा था ना टाइम इक्वल टू 3 दे रखा था ठीक है तो देखो 10 सेकंड जब पास हुआ तब तो ग्रीन हो गया अब अब आप फ्री हो गए नेबर के पास जाने में ठीक है तो और टोटल टाइम कितना लगा इस नेबर प पहुंचने में 10 तो लगा था यहां तक पहुंचने में ठीक है प्लस 3 = 13 यानी कि 13 सेकंड लगेगा इस नेबर तक पहुंचने में ये इंपॉर्टेंट पार्ट था है ना प्लस 3 क्यों किया क्योंकि एज का भी तो हमें कैलकुलेट करना है ना ओके और यह 10 कैसे आ गया क्योंकि भाई अभी आप रेड रीजन पर खड़े हुए थे तो आपको वेट करना पड़ेगा कि नेक्स्ट ये ग्रीन कब होगा तो नियरेस्ट ग्रीन कब होगा वो मैंने ऐसे निकाल लिया मैथमेटिकली 10 होगा तो यानी कि 10 टाइम पास हो चुका था तब तक आप इस चार पे ही खड़े थे इसके नेबर में जाने में आपको 3 सेकंड ऑन लगेगा क्योंकि वो एज है ठीक है एज में ट्रैवर्स करने का 3 सेकंड दे रखा है तो 10 + 3 13 हो जाएगा यहां तक क्लियर है तो ये सबसे इंपॉर्टेंट पार्ट था तो अगर आपको यह समझ में आ गया तो अब आराम से अब आप डाइक्स लगा सकते हो ठीक है अब हम लोग देखो डाा मैं आपको पूरा ड्राय रन करके दिखाऊंगा ताकि आपको अच्छे से क्लियर हो कि कैसे चीजें फ्लो कर रही हैं ठीक है तो एक बार सिंपल सा ड्राई रन करते हैं और इस चीज का ध्यान रखेंगे हम लोग जो डिवीजन वाला हमने चीज पढ़ा ना कब वो रे रेड है कब वो ग्रीन है ठीक है तो देखो डाइर लगाने के लिए मैंने मिन हीप ले लिया और मिन हीप में याद करो दो चीजें शोर करते थे डिस्टेंस कितना लगा इस नोड में पहुंचने के लिए ये मेरा नोड होता था सोर्स से इस नोड में पहुंचने के लिए कितना डिस्टेंस लगा यहां पर डिस्टेंस की जगह टाइम होगा ठीक है तो यहां पर आप इसको टाइम मान लो ओके ठीक है तो हम लोग आते हैं सबसे पहले मैंने क्या बोला कि ओबवियस है ये मेरा सोर्स है तो यहां से मैंने स्टार्ट किया है तो मतलब उस वक्त टाइम कितना हो रखा था जीरो हो रखा था राइट ठीक है तो ओबवियस बात है सोर्स से सोर्स में पहुंचने में जीरो सेकंड लगेगा क्योंकि आप सोर्स पे ही खड़े हो तो कितना टाइम लगा जीरो लगा किस नोड में पहुंचने में जीरो थ वाले नोड में पहुंचने में ठीक है तो ओबवियस एंट्री ये कर देंगे तो और और मुझे d1 में भी जीरो डालना पड़ेगा क्योंकि d1 मतलब इतना जीरो टाइम लगा मुझे इस जीरो नोट के लिए सॉरी जीरो नहीं फर्स्ट नोट के लिए नोट नंबर वन है ना सॉरी न नोट की नंबरिंग वन से ले कर रखी है तो नोट नंबर वन के लिए अब देखो यहां पर d2 में भी यहां पर मैं जीरो नहीं डाल सकता क्योंकि मैंने क्या बोला था d2 का काम क्या है कि ये सेकंड मिनिमम वैल्यू स्टोर करेगा मिनिमम तो जीरो है बट सेकंड मिनिमम जीरो सेम वैल्यू नहीं रख सकते हम लोग तो सिर्फ d1 में मैंने इनिश इज किया है जीरो से ओके ठीक है अब वही डायस पुराना कोड जो डायस का हमने ऑलरेडी पढ़ रखा वही अप्लाई करते हैं सबसे पहले इसको पॉप करेंगे तो पॉप जब करेंगे तो टोटल टाइम पास कितना है वो निकाल लेते हैं टोटल टाइम पास इज इक्वल टू कितना है जीरो है ना देखो तो हां जीरो है और कौन से नोड में पहुंचने का यह टाइम है नोड नंबर वन में पहुंचने का ये टाइम है तो मेरा अभी प्रायोरिटी क से मैंने इसको पॉप कर दिया है ठीक है अब मैं इसके नेबर पर जाऊंगा मान लेते हैं नोड इव है है ना तो इसका नेबर कौन-कौन है देखते हैं वन का नेबर मुझे चलो एक काम करते हैं प्रॉब्लम को थोड़ा सा सिंपल कर देते हैं इस टू को हटा देते हैं एग्जांपल ताकि थोड़ा छोटा हो जाए वन का दो नेबर है मान के चलते हैं एक चार है और वन का एक और नेबर है तीन है ठीक है तो पहले फोर्थ वाले को देखते हैं ठीक है अब देखो न को फोर पर जाना है तो पहले तो यह देखो कि भाई अभी कितना टाइम पास हो चुका है है ना भाई अभी तो जीरो टाइम पास हो चुका है पास हुआ है ठीक है तो याद करो पहले डिव निकालते थे ना टोटल टाइम पास्ड जीरो है डिवाइडेड बाय चेंज चेंज की वैल्यू फाइव हो रखी थी तो जीरो आ गया क्या ये ऑड है या इवन है ये तो इवन है इवन है मतलब अभी आप ग्रीन पर हो और सही बात है आप ग्रीन पर ही हो क्योंकि अभी जस्ट आपने स्टार्ट किया है सब कुछ तो ग्रीन पर हो तो आप आराम से बेफिक्र होके तुरंत मूव कर जाओ अपने नेबर में ठीक है तो मान के चलते हैं आप फोर पर मूव किया जब आपने तो कितना टाइम लगेगा एज में ट्रैवर्स करने में सि 3 सेकंड लगेगा प्रॉब्लम में दे रखा है कि टाइम इज थ्री है तो मैं प्रायोरिटी क्य में डाल दूंगा कि भाई मुझे सोर्स से अ 3 सेकंड लगा कौन से नोड में जाने में फोर्थ वाले नोड में जाने में यहां तक क्लियर है चलो फोर्थ की एंट्री तो हमने मार दी अब हम आ जाते हैं अ थ्री पर ठीक है वन से थ्री पर जा पहले तो देखते हैं डिवीजन कितना अभी टाइम कितना हो रखा है रो टाइम पास हो चुका है और चेंज की वैल्यू कितनी है फाइव है तो यह रो है मतलब अभी तक जीरो बार इंटरवल पास हुआ मतलब पहले इंटरवल पर अभी आप चल रहे हो है ना तो ग्रीन होगा ओबवियस है सिग्नल तो आप आराम से वन से थ्री भी जा सकते हो तुरंत आप थ्री पर चले गए ठीक है और यहां पर कितना टाइम लगा आपको ओबवियस है यहां से यहां जाने में एज बस ट्रैवर्स करना पड़ेगा तो तीन लगता था प्रॉब्लम में दे रखा है एग्जांपल में कौन से नोड में तीन वाले नोड में ठीक है तो यह भी हमने कर दिया अब याद करो हमें d1 भी अपडेट करना पड़ता था ना तो याद करो जब हमने 3 4 यहां पर प्रायरिटी क्य में डाला था तो हमें सबसे पहले यह चेक करना चाहिए था कि थ पर पहुंचने में d1 अपडेटेड है क्या सॉरी फोर्थ वाले नोड के लिए फोर्थ वाले नट के लिए d1 अपडेटेड ही नहीं था तो पहले मैं इस पर अपडेट मारूंगा याद करो इस पर पहुंचने का मुझे मिनिमम डिस्टेंस थ्री मिला था राइट सिमिलरली जब मैं इसको जब मैंने पुश किया होगा तो थर्ड नोट प पहुंचने का मिनिमम डिस्टेंस अभी ये तो इंफिनिटी है तो मुझे अपडेट करना होगा इसको तो पहली बार मैंने अपडेट किया तो बस इसको अपडेट करूंगा d1 को तो यहां पर भी थ्री डाल दिया मैंने यहां तक क्लियर है ओके अब आते हैं नेक्स्ट इटरेशन पर सबसे पहले पॉप करेंगे इसको 33 मतलब टाइम टोटल टाइम पास तीन हो चुका है और करंट नोड मेरा थ्री है तो इसको मैंने पॉप कर दिया ठीक है अब देखते हैं इस नोड का नेबर कौन है इस थ्री का नेबर मुझे दिख रहा है एक तो वन है दोबारा से ठीक है क्योंकि प्रॉब्लम में दे रखा कि आप किसी भी नोड को दोबारा भी विजिट कर सकते हो और दूसरा नोड क्या है फोर है है ना ठीक है दूसरा नोड मेरा फोर है अब एक चीज ध्यान देना पहले वन पर आते हैं ओके तो अब पहले तो यह देखते हैं कितना टाइम पास हो चुका है डिवीजन निकाल लेते हैं कितना इंटरवल पास हो चुका है टोटल टाइम पास है तीन मेरा हर कितना सेकंड पे इंटरवल चेंज होता है 5 सेकंड पे तो अभी ज़ीरो है इसकी वैल्यू मतलब अभी भी मेरा इंटरवल चेंज नहीं हुआ है अभी भी मैं ग्रीन पर ही होगा है ना रो आया डिवीजन मतलब यह इवन है ना मतलब मैं ग्रीन पर हूं अभी ठीक है और अगर मैं ग्रीन पर हूं इसका मतलब क्या हुआ कि मैं आराम से तुरंत पास कर सकता हूं तो थ्री से आप वापस से वन जा सकते हो आराम से अपने नेबर के पास ठीक है तो अब देखो ध्यान देना वन में जाने का मुझे एक नया डिस्टेंस मिल चुका है ऑलरेडी टाइम पास कितना था तीन हो रखा था टाइम पास ऑलरेडी तीन था ना प्लस अभी वन पर दोबारा जब जाओगे तो तीन लगेगा क्योंकि एज को ट्रैवर्स करने में तीन लगता था तो कितना हो गया टोटल छह हो गया अब एक बात बताओ इस वन वाले नोड में पहुंचने का मिनिमम डिस्टेंस कितना था रो था क्योंकि देखो d1 में ऑलरेडी अपडेटेड है वो तो यस मैं d1 को दोबारा अपडेट नहीं करूंगा क्योंकि ऑलरेडी मिनिमम डिस्टेंस इसमें अपडेटेड होगा तो मैं ये चेक कर लूंगा कि अच्छा d1 में यहां पर इंफिनिटी नहीं है मतलब ये अपडेट ऑलरेडी तो मैं d2 में चेक करूंगा अच्छा d2 में अपडेटेड नहीं है तो ओबवियस बात है d2 में मैं अपडेट कर दूंगा ये मैं यहां पर छ डाल दिया कि भाई वन वाले नोड में पहुंचने का सेकंड मिनिमम डिस्टेंस जो है ना वो छ है यहां तक क्लियर है ओके तो सिंस मैंने अभी इसको यहां पर अपडेट मारा है तो मुझे प्रायोरिटी क में भी इसको डालना चाहिए ठीक है कि भाई डिस्टेंस क्या था छ था इसको मैं ऊपर लिख देता हूं 3 4 को ऊपर लिख देता हूं और अभी यहां लिख देता हूं कि डिस्टेंस छ मिला है किस नोड में पहुंचने का वन वाले नोड में पहुंचने का और मेरा सेकंड मिनिमम डिस्टेंस है ठीक है और मिनिमम डिस्टेंस मेरा ये जीरो था जो मैंने स्टार्टिंग में ही डाल दिया था तो वन का तो काम हो गया अब आ जाते हैं फोर्थ वाले नोट पर कि भाई थ्री से मुझे फोर जाना है तो सबसे पहले देखते हैं टाइम पास कितना हुआ है टाइम पास मेरा तीन हुआ है अभी तक मैं अभी भी कौन से सिग्नल में हूं वो देख लेता हूं टाइम पास बाय फ दैट इज जीरो जीरो मतलब और ये इवन नंबर है मतलब अभी भी मैं ग्रीन सिग्नल में हूं मैं तुरंत भाग सकता हूं वेट नहीं करूंगा मैं तो फोर पर आ गया ठीक है तो फोर पर जब आया तो तीन ऑलरेडी टाइम पास तीन हो था अब फोर पर ट्रैवर्स किया तो इस एज पे ट्रैवर्स किया तो 3 सेकंड लगा होगा ए ट्रैवर्सल के लिए तो छ हो गया सेकंड यानी कि 6 सेकंड पास हुआ तब आप फोर पर आ चुके होंगे ठीक है तो पहले तो देखते हैं d1 में फोर पे पहुंचने का डिस्टेंस अपडेटेड है क्या 3 + 3 6 था ना ठीक है तो d1 में मैंने देखा कि अच्छा फोर में पहुंचने का मिनिमम डिस्टेंस तीन ऑलरेडी है तो मैं इसको क्यों अपडेट करूंगा दोबारा नहीं करूंगा क्योंकि इस d1 में मिनिमम डिस्टेंस है तो ओबवियस सी बात है अब मुझे क्या करना होगा d2 में जो मिनिमम डिस्टेंस है ना वो यहां स्टोर करना पड़ेगा तो यहां पर देखो छ मैंने स्टोर कर दिया कि अब जो डिस्टेंस आया d2 में डाला है मैंने और वो सेकंड मिनिमम वैल्यू हो गया इस फोर प पहुंचने के लिए ठीक है और आपको साफ साफ दिख भी रहा होगा सही बात है देखो फोर प पहुंचने का मिनिम डिस्टेंस तीन है और सेकंड मिनिमम डिस्टेंस यहां पर छ है ओके ग्राफ में भी आपको देख के समझ में आ जाएगा ठीक है यहां तक तो क्लियर हो गया तो अब आपने फोर में यह एंट्री डाली है तो मुझे हीप में भी डाल देना चाहिए वो एंट्री कि भाई कितना है डिस्टेंस इस 3 फ को पहले तो ऊपर कर देते हैं डिस्टेंस छह था और नोड नंबर अ फोर था ना तो फोर को यहां डाल देते हैं और वन को यहां डाल देते हैं क्योंकि अगर वैल्यू जब ये जब पहला वैल्यू सेम रहता है ना तो प्रायोरिटी की क्या क्या करेगा मिन हीप है ना तो सेकंड वैल्यू के हिसाब से सॉर्ट कर देगा तो बस मैंने सेकंड हा के सॉर्ट कर दिया कोई फर्क नहीं पड़ता इससे ठीक है ओके तो ये मैंने डाल दिया यहां पर अब इसका भी काम हो गया फोर का ओके इसको पॉप करते हैं अब आया नेक्स्ट मेरा नोट देखो तो ये आया पहला टाइम पास तीन है और अभी मैं फोर्थ वाले नोट पर खड़ा हूं ओके तो मैंने इसको पॉप कर दिया अब देखते हैं सबसे पहले कि फोर्थ का नेबर कौन-कौन है फोर्थ का नेबर एक मुझे तीन दिख रहा है और एक फोर का नेबर मुझे वन दिख रहा है और एक फोर का नेबर मुझे फाइव दिख रहा है ठीक है अब देखना इंपॉर्टेंट पार्ट है ये थोड़ा इंपॉर्टेंट है यहां पर पूरा फोकस करना पहले फोर से वन का देखते हैं इस वन का ठीक है तो अभी टोटल टाइम पास कितना है तीन हो रखा है तीन हो रखा है ना उसको चेंज से डिवाइड करते हैं कितना इंटरवल पास हुआ वो पता करने के लिए 5 0 मतलब अभी भी आप ग्रीन सिग्नल पे हो क्योंकि टोटल टाइम पास तीन हुई तीन ही हुआ है अभी तक रेड कब होगा जब पांच हो जाएगा पांच के बाद होगा रेट तो अभी तो आप तीन पे ही हो मतलब दोबारा आप वन पे जा सकते हो दोबारा वन पे जाओगे तो टोटल टाइम पास अभी कितना है तीन है दोबारा वन पे जाने पे आपको एक्स्ट्रा तीन लगेगा एज ट्रैवर्स करने के लिए तो छ हो गया तो वन पे पहुंचने का मुझे एक डिस्टेंस मिला है छ ठीक है तो देखते हैं मैंने d1 पे गया मैं बोला कि अच्छा यहां पर तो रो है तो भाई यह मिनिमम है इसको मैं नहीं छूंगा d2 में ऑलरेडी छह है यार तो क्या क्या ही करोगे छोड़ दो इसको अपडेट ही नहीं करेंगे इसको तो वन तो गया ठीक है अब मैं आ जाता हूं थ्री पर ठीक है तो फोर से मुझे थ्री जाना है और अभी टाइम पास थ्री ही हो रखा है मतलब अभी-अभी आप ग्रीन ग्रीन सिग्नल पर हो ठीक है ओके जब आप फोर से थ पर गए तो देखते हैं फोर से थ जाने प आपको 3 प् 3 6 लग जाएगा तो आप d1 पे पहले देखे तो यहां पर थ्री है ऑलरेडी तो अपडेट नहीं करोगे बट d2 में हमने देखा कि अच्छा इंफिनिटी है तो मैंने यहां पर छ डाल दिया ठीक है कि थ्री पर पहुंचने का आपको एक सेकंड मिनिमम डिस्टेंस मिल चुका है जो कि छ है ठीक है और सही बात है ी पर आपका सेकंड मिनिमम डिस्टेंस छ होना चाहिए ी पर पहुंचने का ऐसे गए और ऐसे चले गए ठीक है ठीक है तो सेकंड और मिनिम ये फर्स्ट मिनिम सेकंड मिम दोनों मिल गया तीन प पहुंचने का तो अब से मुझे य इसको स्टोर भी कर देना चाहिए कि सिक्स यह ्र यहां आ जाएगा और सव एक नया एंट्री मैंने डाल दिया यहां पर तो मैंने इसको अपडेट कर दिया प्रायोरिटी क्य में भी ठीक है ओके तो थ्र का भी काम हो गया अब आ जाते फ प जो हमारा टारगेट नड है अभी आप फाइव पर आए हो ओके तो देखते हैं पहले तो अभी मेरा लैप्स टाइम तीन है ना लैप्स टाइम मेरा तीन है तो ओबवियस अभी आप ग्रीन सिग्नल पर हो क्योंकि तीन बा चेंज जब करोगे तो जीरो आएगा मतलब ग्रीन सिग्नल पर हो आप ये इवन नंबर है ठीक है तो जीरो इवन है तो मतलब ग्रीन पर हो तो मतलब आप थ्री से मतलब आप फाइव पे जा सकते हो ना तो फाइव पर जब जाओगे तो 3 + 3 दैट इज छ लगेगा राइट तो देखते हैं फाइव पे पहुंचने का मिनिमम डिस्टेंस कितना है इंफिनिटी है भाई तो ओबवियस सी बात है इसको मैं अपडेट कर दूंगा यहां पर छ कर दूंगा यहां तक क्लियर है ओके अब जब यहां पर आपने किया तो इसको अपडेट कर देना कि भाई छ है और पांच है ना तो इसको मैं सबसे नीचे डाल देता हूं छमा चर था ऑलरेडी यहां पर छ डिस्टेंस है पांच पर पहुंचने का इसको मैंने हीप में डाल दिया ठीक है ओके यह भी काम हो चुका है मेरा गॉट इट अब हम लोग आगे बढ़ते हैं अब आया 6 व ठीक है टाइम पास है छ नोड है मेरा वन अब देखो सबसे पहले वन पर है अभी वन से कहां-कहां जा सकते हैं थ्री जा सकते हैं और वन से फोर जा सकते हैं ठीक है अब देखो ध्यान देना बहुत इंपॉर्टेंट है ये पार्ट कि अभी टाइम पास मेरा छह हो रखा है छह मतलब एक इंटरवल पास हो चुका होगा 5 सेकंड का उसके बाद एक और इंटरवल जो है 5 सेकंड का उसमें बस आप एक सेकंड गुजरा है मतलब अभी आप रेड में ही फंसे हुए हो वो मैं कैसे पता करूंगा ऑड इवन से चेक कर लूंगा 6/5 करोगे तो वन आ जाएगा मतलब ये ऑड है मतलब अभी आप रेड में फंसे हुए हो तो आपको वेट करना पड़ेगा तो कितना टाइम पास हो जाएगा वेट करते करते वो कैसे निकालेंगे 6/5 का वैल्यू वन आया था उसमें प्लस वन कर दो और मल्टीप्ला बाय चेंज कर दो चेंज का कितना था वैल्यू पाच था ना तो 10 हो गया मतलब टाइम पास की वैल्यू अब चेंज हो जाएगी टाइम पास की वैल्यू आपको अपडेट करके 10 कर देना पड़ेगा ठीक है कि अब नेक्स्ट आप थर्ड सॉरी आप वन पर हो ना तो नेक्स्ट अब आपको 10 सेकंड जब गुजरेगा तब आप फ्री हो पाओगे तब जाकर आप इस फोर पर ट्रैवर्सल मार सकते हो है ना य वन से आप अपने थ्र पर या फिर फोर पर तब जाकर आप ट्रैवर्स कर पाओगे तो ओबवियस सी बात है अब जब 10 सेकंड गुजर जाएगा आप थ पर जाओगे तो देख रहे हो 10 3 13 हो जाएगा ना 13 तीन पर पहुंचने का 13 सेकंड भाई साहब यह तो मिनिमम तो तीन है और सेकंड मिनिमम भी छ है तो 13 मैं क्यों ही डालूंगा छोड़ो इसको ठीक है तो तीन तो गया सिमिलरली 10 सेकंड जब गुजर जाएगा तो आप चार पर जा सकते हो तो चार पर जाओगे तो तीन सेकंड और लगेगा एज ट्रैवर्सल के लिए 13 तो चार पर पर पहुंचने का 13 सेकंड भाई चार पर पहुंचने का मिनिमम है 3 सेकंड सेकंड मिनिमम है 6 सेकंड तो मैं दोबारा अपडेट ही नहीं करूंगा देख रहे हो फ्यूचर में जो वैल्यूज आ रहे हैं वो बड़े ही वैल्यू आ रहे हैं तो मुझे दोबारा इस d2 को अपडेट करने की जरूरत ही नहीं पड़ रही है सेकंड मिनिमम जो निकल गया वही मेरा बेस्ट वैल्यू है ठीक है ओके तो मैंने किसी को यहां कुछ अपडेट नहीं किया कहानी इधर ही खत्म हो गया अब मैं 63 को निकालता हूं 6 3 है ना तो थ्री का नेबर कौन-कौन है देखते हैं थ्री का नेबर है वन है थ्री का नेबर है फोर फिर से वही चीज होगा देखो ये सिक्स है ना टाइम पास तो यस है नेक्स्ट ग्रीन सिग्नल होगा कब 10 सेकंड में होगा ठीक है तो 10 सेकंड के बाद आप एक एज ट्रैवर्सल मारोगे वन पे पहुंचने के लिए तो 13 हो जाएगा तो यस है ना आप इसको अपडेट करोगे ना इसको अपडेट करोगे ठीक है सिमिलरली दूसरा देखो चौथा फोर्थ नोड में पहुंचने के लिए आपको कितना टाइम लगेगा 10 तो टाइम पास हो चुका है तीन लगेगा ए में 13 हो गया तो फोर्थ नोड प पहुंचने के लिए 13 सेकंड भाई यहां आप इसको अपडेट करोगे नहीं यहां पर अभी आप इसको अपडेट करोगे नहीं क्योंकि ऑलरेडी वो मिनिमम और सेकंड मिनिमम वैल्यू पर है देखो ये सब भी अपडेट नहीं कर पाएंगे हमारे मिनिमम को और सेकंड मिनिमम वैल्यू को ठीक है ओके यहां तक तो क्लियर है उसके बाद देखते हैं 6स 4 आया 6 4 ठीक है अब देखना ध्यान देना 6 4 है मतलब फोर से अब आप कहां कहां जा सकते हो फोर से आप थ्री जा सकते हो फोर से वन जा सकते हो फोर से फाइव जा सकते हो बट ये टाइम पास देखो सिक्स हो चुका है तो मुझे नियरेस्ट टाइम देखना पड़ेगा जब ये ग्रीन हो सके क्योंकि अभी ये ऑड है ना 6/5 करोगे तो वन आएगा तो ये ऑड है तो नियरेस्ट टाइम कब है जब ये ग्रीन होगा इवन हो जाएगा 10 10वें वाले टाइम पे तो 10 सेकंड पास हो चुका है तीन पर जाने तीन पर अगर आपको जाना है इस थर्ड नोट पे तो 13 सेकंड लगेंगे तो यह भी गुड नहीं है यह भी गुड नहीं है तो अपडेट नहीं करूंगा वन पे जाने के लिए 10 3 13 सेकंड लगेगा फिर से तो अब यह भी अच्छा नहीं है यह भी अच्छा नहीं है तो अप डेट नहीं करेंगे ऑलरेडी ये 0 और सिक्स है ठीक है फिफ्थ वाले नोड में जाने के लिए कितना लगेगा देखते हैं देखो ध्यान देना बहुत इंपॉर्टेंट है टाइम पास 10 हो रखा था फिफ्थ नोट पर अब आपको जाना है तो 3 सेकंड लगा दैट इज 13 सेकंड आपने d1 पे पहले देखा कि पाच नोड में पहुंचने के लिए 6 सेकंड लग रहा है भाई ये तो मिनिमम वैल्यू है ऑलरेडी और मुझे अभी 13 मिला है ठीक है तो मैं d2 में चेक कर लूंगा वहां इंफिनिटी है तो मैंने यहां 13 डाल दिया अब देखो ध्यान दो इस फिफ्थ नोड में पहुंचने का मुझे मिनिमम वैल्यू मिल चुका है अब फ्यूचर में मुझे इससे बेटर वैल्यू नहीं मिलेगा ठीक है अब देखो ध्यान देना मैंने अभी जस्ट इसको अपडेट किया है तो ओबवियस है मैं इसको डाल दूंगा यहां पर 65 को मैं यहां डाल देता हूं ऊपर अब देखो क्या मिला मुझे यह 13 डिस्टेंस मि मिला है और किस नोट प पहुंचने का फिफ्थ नोट प पहुंचने का यहां तक क्लियर है ओके तो हमने सबका कर दिया अब नेक्स्ट मेरा क्या है 6 5 है 6 नोड = 5 ठीक है अब देखो ध्यान देना यहां पर अभी आप जिस नोड पर आए हो फ ये मेरा डेस्टिनेशन नोड है है ना ओबवियस स बात है ये मेरा n है n डेस्टिनेशन नोड तो आप चेक कर लेना कि क्या मेरा करंट नोड डेस्टिनेशन नोड के बराबर है यस बराबर तो है बट आपको यह भी देखना पड़ेगा कि क्या इस डेस्टिनेशन नोड का सेकंड मिनिमम वैल्यू निकल रखा है क्या देख लेते हैं d2 में जाएंगे देखेंगे डे यस निकल रखा है तो यही मेरा आंसर होगा इससे बेटर आंसर मिल भी नहीं पाएगा ना फर्द क्योंकि 13 है अभी फ्यूचर में और कोई अगर आता भी है तो 13 प्लस समथिंग होगा ना क्योंकि टाइम पास इतना हो चुका है 13 फ्यूचर में जब कोई वैल्यू अपडेट भी होगी तो 13 प्लस एज में ट्रैवर्सल जो भी करोगे तीन 16 हो जाएगा तो ओबवियस है बड़ा ही वैल्यू मिलेगा तो आप यहीं पर रुक के रिटर्न कर सकते हो अपने आंसर को तो बस आप यहां पर ये चेक कर लेना कि नट = n है मतलब टारगेट नोड में आप पहुंच चुके हो हां और d2 ऑफ n या d2 ऑफ नोड हमने निकाल रखा है क्या हां ये नॉट इक्वल टू इंट मैक्स है नॉट इक्वल टू इंट मैक्स है तो आराम से रिटर्न d2n कर देना इसी वक्त क्योंकि फ्यूचर में और आगे जाओगे कोई फायदा नहीं है कोई पॉइंट ही नहीं है इधर ही ब्रेक करके रिटर्न कर दो आंसर को d2n की वैल्यू पहले इनफिनिटी थी अभी 13 हो चुका है मतलब हमने इसकी ऑप्टिमल वैल्यू निकाल दी है ठीक है अब फ्यूचर में इससे ऑप्टिमल वैल्यू नहीं मिलेगा आपको है ना अगर आपको ड अम में भी मैंने बताया था आपको कि फ्यूचर में और ऑप्टिमल वैल्यू मिल ही नहीं सकता क्योंकि देखो अभी इसका टाइम पास 13 है ठीक है फ्यूचर में जो भी इस नट पर आएगा तो 13 प्लस समथिंग करके आएगा ना तो यस है इससे बेटर आंसर नहीं मिलने वाला ठीक है यह मेरा सेकंड मिनिमम वैल्यू तो इसी वक्त मैंने d2n प रिटर्न कर दिया सिंपल सा सलूशन था देखा जाए तो ज्यादा कुछ टफ नहीं है नॉर्मल डायस तर है बस हम ये टाइम पास छ जो था ना छ ये देख रहे हो मैंने कैसे निकाला कि कितना इंटरवल है अभी 6 बा 5 कर दिया चेंज चेंज की वैल्यू फ थी ना तो फ इ तो कितना हो 6 बा फव हो गया वन ऑड है मतलब अभी आप रेड वाले रीजन में तो रेड वाले रीजन में मतलब आपको थोड़ा सा वेट और करना पड़ेगा तो कितना वेट करना पड़ेगा इसी में प्लस व कर दो और इनटू चेंज मल्टीप्लाई कर दो तो मतलब दव सेकंड में आप फ्री हो जाओगे फिर ग्रीन हो जाएगा फिर ये ट्रिकी पार्ट था इस प्रॉब्लम का ट्रिकी क्या नर्मल मैथमेटिकल पार्ट था इसके अलावा बाकी सारी चीजें आसान थी तो अभी मैं डाय एल्गोरिथम को जो कोड करूंगा एटली वही स्टोरी मैं रिपीट करूंगा जो मैंने यहां पर आपको बताया ड्राई रन में ठीक है जल्दी से उसको कोड करते हैं उसके बाद इसके नेक्स्ट अप्रोच पर आएंगे तो चलो इसका कोड करते हैं मैंने एडजेसेंसी लिस्ट पहले ही बना दिया है यहां पर देखो अनॉर्डड मैप ले लिया है और उसका u एज को पुश कर दिया उसमें ठीक है इसके बाद मैंने क्या बोला था कि दो वेक्टर लेंगे वेक्टर ऑफ इंट d1 ठीक है जिसका साइज n + 1 रख रहे और n + 1 क्यों रख रहे हैं क्योंकि जो नोड की नंबरिंग है वो वन से लेकर n है ठीक है तो n+ 1 साइज ले लिया इंट मैक्स यहां पर डाल देते हैं सिमिलरली वेक्टर ऑफ इंट डीटू ए प्सव इंट अंडरस्कोर मैक्स यहां तक क्लियर है इसके बाद ऑस डा आपको करना है प्रायोरिटी क्य लेना पड़ेगा आपको प्रायोरिटी क्यू सॉरी यहां पर पेयर डालते थेना हम लोग तो ऊपर पहले डिफाइन कर देते हैं श डिफाइन पेयर ऑफ इंट कमा इंट इसको क्या नाम दे दे इसका नाम दे देते हैं प ठीक है ताकि बारबार यहां लिखना ना पड़े तो यहां पर प्रा की ऑफ प वेक्टर ऑफ प और सिंस हमें मिन हीप बनाना है तो हम लोग क्या लगाते थे ग्रेटर प राइट ग्रेटर प यह मैंने प्रायोरिटी क्यू बना लिया है और प्रायोरिटी क्यू में मैं पुश करूंगा दो चीजों को पहला कि कितना डिस्टेंस लगा है और किस सोर्स से मैंने स्टार्ट किया है राइट कौन सा नोड है ठीक है तो अब व ऑफव मैंने जीरो कर दिया ठीक है वाइल नॉट ऑफ प क नॉट ऑफ प कड एमटी तब तक चलाएंगे जब तक यह प्रायोरिटी मेरा खाली नहीं ता तो ऑटो अब इसमें दो चीज मुझे मिलेंगे पहला टाइम पास कितना हुआ है अभी तक इस नोड में आने में और यह नोड कौन सा है ठीक है प कडॉट टॉप प कड पॉप ठीक है और मैंने क्या बोला था कि हमेशा चेक कर लेना ना कि अगर d2 ऑफ सॉरी अगर करंट नोड जो है मेरा वो एगजैक्टली डेस्टिनेशन के बराबर है एंड मैंने उसका d2 निकाल रखा है d2n इज नॉट इक्वल टू इंट अंडर मैक्स तो यस बात है हमने आंसर निकाल दिया होगा रिटर्न d2 ऑफ n ठीक है इतना टाइम लगेगा ओके ये मेरा सेकंड मिनिमम वैल्यू मैं d2 में ही स्टोर करता था आपको याद होगा ठीक है अब अगर ऐसा नहीं है तो ओबवियस सी बात है पहले तो हम निकालेंगे मेरा डिवीजन वाला फैक्टर कि कितना टाइम पास हो चुका है डिवाइडेड बाय चेंज ठीक है और यह चेक कर लेंगे कि क्या मेरा डिव जो है परसेंटाइल 2 इ ट इ टव है मतलब यह ऑड है ऑड मतलब कि अभी मैं रेड सिग्नल पर खड़ा हूं रेड पर खड़ा हूं तो मैं कब फ्री होंगा टाइम पास्ड विल बी इक्वल टू याद करो चेंज मल्टीप्ला बाय डिव प्व यही मैंने सिखाया था आपको तो नेक्स्ट कब टाइम पर मैं ये रे ग्रीन सिग्नल आ जाएगा वो मुझे मिल चुका है अब मैं इसके सारे नेबर पर चला देता हूं ऑटो एंड नेबर इन एडीजे ऑफ करंट नोड ठीक है अब मुझे बस इतना देखना है कि d1 में इस नेबर का वैल्यू ऑलरेडी जो है अगर वह मेरे करंट टाइम पास्ड से बड़ा है टाइम पास नहीं टाइम पास प्लस इस नेबर पर पहुंचने में जो एज लगेगा मुझे एज प ट्रैवर्स भी कर रहा तो प्लस टाइम करना पड़ेगा ठीक है अगर ऐसा है तो ओबवियस बात है तो d2 नेबर में मैं d1 नेबर की वैल्यू डाल दूंगा ताकि सेकंड मिनिमम वैल्यू d2 नेबर में चला जाए और डी व नेबर में मैं टाइम पास्ड प्लस टाइम स्टोर कर दूंगा यहां तक क्लियर है और प कडॉट पुश कर दूंगा कि भाई मैंने अभी टाइम पास्ड प्लस टाइम स्टोर किया है फॉर किस कौन वाला नोट इस नेबर वाले नोट के लिए यहां तक क्लियर है और अगर ऐसा नहीं है तो एल्स इफ देखो क्या चेक करेंगे हम लोग सबसे पहले ये चेक करेंगे कि d2 ऑफ नेबर का जो भी वैल्यू है अगर वो मेरे टाइम पास्ड प्लस टाइम से बड़ा है ठीक है लेकिन एक चीज इंश्योर करना पड़ेगा किव ऑफ नेबर का जो वैल्यू है वो इसके बराबर नहीं होना चाहिए राइट नॉट इक्वल टू टाइम पास्ड प्लस टाइम तब सेम वैल्यू नहीं रखना याद याद करो मैंने आपको बताया था तो यस तभी हम इसको स्टोर करेंगे टाइम पास्ड प्लस टाइम ठीक है और उसको पी क में फिर पुश कर देंगे पड पुश यहां पर टाइम पास्ड प्लस टाइम कौन सा नोड है नेबर नोड य तक क्लियर है और लास्ट में बस जब सब कुछ खत्म हो जाएगा तो रिटर्न माइनस व कर दो जबक आंसर आपको इधर से आ जाएगा रिटर्न डीट इस लाइन नंबर 25 से ठीक है तो इसको सबमिट करके देखते व शुड बी एबल टू पास ल द केसेस लेट सी इनडीड यस वी हैव सॉल्व ऑल दी टेस्ट केसेस अब देखो ध्यान दो यहां पर स्पेस हमने लिया है ना ओ ऑफ अ स्पेस मैंने लिया है o ऑफ v प् e क्योंकि हमने पूरा ग्राफ बनाया राइट ये मेरा स्पेस कॉम्प्लेक्टेड ऑफ वर्टिस और आपको पता होगा कि डाइक्स एल्गोरिदम मेरा कितना टाइम लेता है o ऑफ e * लॉग ऑफ v है ना मतलब जहां पर e नंबर ऑफ एजेस है और v नंबर ऑफ वर्टिसेज है और हर नोट को हम दो बार विजिट कर रहे हैं तो मतलब इसका टवा इस आप बोल सकते हो ए टोटल मल्टीप्ला बायट बट टू एक कांस्टेंट है तो उसको मैं हटा दे रहा हूं a * लॉग v टोटल टाइम कॉम्प्लिटीशन लग रहा है देखो यहां पर आप ट्रैवर्सल कर रहे हो ना ठीक है यहां तक क्लियर है ओके तो जल्दी से अब आ जाते हैं अपने नेक्स्ट अप्रोच पर अब देखो इसके अप्रोच टू पर आते हैं यानी कि बीएफएस से भी इसको सॉल्व किया जा सकता है क्या वो देखो या देखा तो प्रॉब्लम बीएफएस से हमारे मन में आना चाहिए था पहले भी कि बीएफएस से सॉल्व किया सकता क्यों क्योंकि य शॉर्टेज पाथ की बात हो रही है और यहां पर अगर आप एक चीज नोटिस करो कि यह जो मान लेते हैं ये मेरा ग्राफ दे रखा है मान के चलो कि ऐसा ग्राफ दे रखा आपका यहां पर हर एक चीज देख रहे हो यूनिफॉर्म है मतलब एट द सेम टाइम यह सारे लोग रेड होते हैं और एट द सेम टाइम यह सारे लोग ग्रीन होते हैं ठीक है तो मान के चलो कि ये अगर आपका सोर्स है और मानने चलते हैं ये आपका डेस्टिनेशन है कहीं पर ठीक है या फिर ऐसे मान के चल लो कि यहां पर कहीं फर्द जाके आपका यह डेस्टिनेशन है ठीक है तो अगर आप बीएफएस लगाते हो तो यहां पर आप इस सोर्स से स्टार्ट करोगे बीएफएस है ना क्यू पे डालोगे इस सोर्स को ठीक है तो पहले लेवल जब क्रॉस हो जाएगा तो बीएफएस में याद करो लेवल वा ट्रैवर्सल करते हैं तो पहला लेवल जब क्रॉस करेंगे तो देखो 3 सेकंड लगेगा मान के चलते हैं ठीक है और जो भी पाथ है एक तो पाथ मुझे ये दिख रहा है यह वाला पाथ जो ऐसे करके जा रहा है और एक पाथ ये दिख रहा है तो दोनों में देखो कोई डिफरेंस नहीं है इस वाले पाथ में भी मुझे तीन ही ट्रैवर्सल करना पड़ा क्योंकि हर एच की ट्रैवर्सल का टाइम तीन ही सेकंड है और दोनों यहां पर और यहां पर मैं सेम टाइम पर पहुंचा हं राइट क्योंकि सेम लेवल पर है दोनों और अगर यहां पर रेड हुआ तो मुझे दोनों नोड में वेट करना पड़ेगा क्योंकि रेड दोनों में साथ में होगा ठीक है हर नोड में साथ में रेड होता है और हर नोड में साथ में ग्रीन होता है और सारे जज का ट्रैवर्सल भी सेम है तो भाई नॉर्मल बीएफएस लगाने में क्या दिक्कत थी क्यों हम डाय एक्स्ट्रा का सर दर्द ले रहे थे है ना तो आईडियली नॉर्मल बीएफएस से आपको पहले बनाना चाहिए था इस प्रॉब्लम को ठीक है तो देखते हैं नॉर्मल बीस कितना आसान करता है हमारे प्रॉब्लम को मैं यहां पर गया इसके बाद फिर नेक्स्ट लेवल इसका ये ये होगा इसका नेक्स्ट लेवल ये होगा इन तीनों को ट्रैवर्स करेंगे फिर किसी पाथ से य ये निकलेगा तो ओबवियस फिर से वही करेंगे दो डिस्टेंस ले रखेंगे एक d1 और एक d2 ठीक है तो d2 का मिनिमम डिस्टेंस यहां पर कुछ स्टड होगा और सेकंड मि इसमें कुछ स्टोर्ड होगा और वही मेरा आंसर होगा d2 वाला सेम डायस जैसा ही लॉजिक लगाएंगे d1 और d2 को ये अपडेट करने के लिए बट मैं बोल रहा हूं कि नॉर्मल बीएफएस से भी इसको सॉल्व किया जा सकता था वेरी इजली है ना कोई कोई एक्स्ट्रा दिमाग ही नहीं लगाना पड़ा मुझे देख रहे हो मतलब मैं नॉर्मल अ ये एक क्यू ले लूंगा ठीक है उसमें इस सोर्स को डालूंगा ठीक है सोर्स को डाल दिया और यहां से बीएफए स्टार्ट कर दूंगा ठीक है और जब भी मैं पहुंच अपने टारगेट नोट पर तो मैं पहले तो ये चेक कर लूंगा कि मेरा टारगेट नोड अभी मतलब जो नोड है मेरा डेस्टिनेशन नोड उसका अगर d2 पॉपुलेशन अभी तक नहीं हुआ है तो मतलब हमें आंसर अभी तक नहीं मिला है ठीक है जैसे ही मुझे d2 पॉपलेट हो जाएगा उस टारगेट नोट का मैं उसी वक्त उस टारगेट d2 ऑफ दैट टारगेट नोट रिटर्न कर दूंगा याद करो अभी जो डा एक्स्ट्रा में हमने किया था सेम चीज यहां पर भी करूंगा राइट ओके और यहां पर भी टाइम वाला सीन सेम चीज होगा जो वहां पर मैं निकाल रहा था डिवीजन इज इक्वल टू टाइम पास्ड बाय चेंज और अगर मैं रेड में हूं अगर यह ऑड है तो मैं रेड में हूं अगर रेड में हूं तो मुझे वेट करना पड़ेगा तो कैसे निकाल देते डिवीजन + 1 इंटू अ जो भी है मेरा चेंज है ना चेंज की वैल्यू वो चीज सारी चीजें सेम होगी कुछ नया चीज नहीं कर रहे हैं तो बीएफएस इज द सिंपलेस्ट कोड एंड द सिंपलेस्ट अपो अप्रोच टू सॉल्व दिस प्रॉब्लम ठीक है तो ज्यादा दिमाग लाने की जरूरत भी नहीं है नॉर्मल बीएफएस लगाएंगे उसी से ये सॉल्व हो जाएगा ठीक है जब अभी हम लोग जब कोड करेंगे इसको बीएफएस का तो नॉर्मल बीएफएस लगाएंगे कोई एक्स्ट्रा दिमाग नहीं लगाएंगे देखना ये प्रॉब्लम सॉल्व हो जाएगा अब देखो यहां पर ध्यान दो मैंने नॉर्मल सा एग्जांपल ले लिया पहले मैंने सोर्स को यहां पर पुश कर दिया ठीक है अपने q में ये मेरा q है d1 d2 इनिश इज कर दिया सबको अ और यहां पर याद करो d1 का वन को हम ज़ीरो से इनिश इज करते थे जो मैंने डायरा में किया था ठीक है तो सबसे पहले वन को मैंने पॉप किया तो ये मेरा वन नोड है ठीक है अब एक बात बताओ इस वन को मैं कितनी बार विजिट कर रहा हूं इस वन को मैं एक ही प ये मेरा पहला विजिट है इस वन का राइट और ये मेरा टारगेट नोट भी नहीं है ओके तो अब अब देखो ध्यान दो टाइम पास्ड की इंफॉर्मेशन अभी तक तो मैंने निकाली नहीं है टाइम पास की इंफॉर्मेशन ठीक है तो टाइम पास मेरा कितना होगा वो देखो अभी तक d1 ये मेरा फर्स्ट नोड है ना ठीक है तो अभी मैंने इसको पहली बार विजिट किया है तो इसका टाइम पास जितना होगा वही मेरा टाइम पास होगा अभी इतना पा टाइम पास हो चुका है अभी ओबवियस बात आप वनत पहले वाले नोट पर खड़े हो तो कितना टाइम पास हुआ है जीरो नोट पास हुआ है ठीक है तो मैंने जीरो यहां पर निकाल लिया ठीक है कैसे निकाला देखो यहां पर मैं लिख देता हूं कि टाइम पास्ड इक्वल टू d1 ऑफ जो भी नोड मेरा करंट नोड वन है ना ट इ जीरो तो अभी यस मेरा टाइम पास जीरो है ठीक है अब एक बात बताओ इसके बाद अगर दोबारा मैं मुझे यह वन नोड मिलता है फ्यूचर में कभी भी ठीक है तो मैं उस वक्त क्या देखूंगा कि अच्छा d1 तो ऑलरेडी पॉपलेट है बट दोबारा अगर वो वन आ गया तो मैं उस केस में क्या करूंगा d2 वाला टाइम यहां पर लूंगा यहां पर d1 नहीं लूंगा उस केस में उस केस में मैं d2 लूंगा क्यों क्योंकि भाई d1 तो ऑलरेडी मैंने निकाल रखा है और ये बीएफएस से मैंने निकाला तो मैं गारंटीड है कि ये मिनिमम वैल्यू होगा मुझे चेक करने की जरूरत भी नहीं है कि मिनिमम है कि नहीं ठीक है बीएफएस से निकाला है तो मिनिमम टाइम में ही हम लोग पहुंचेंगे ठीक है फ्यूचर में कोई नया वैल्यू आके इसको अपडेट करके इसको और छोटा नहीं कर पाएगा क्योंकि ये अ बीएफएस से हम लोग कर रहे हैं और यहां पर आप एक और इंफॉर्मेशन भी स्टोर कर सकते हो कि जो मेरा अ करंट वाला नोड है मतलब जैसे मान लेते हैं यह मेरा नथ वाला नोड है ना ये अभी तक कितनी बार विजिट हुआ है ठीक है इसकी भी इंफॉर्मेशन आप यहां स्टोर कर सकते हो तो अब यहां वनव स्टोर कर सकते हो अपने क्यू में जहां पर पहला एंट्री क्या है ये मेरा नोड है कि मेरा नोड वन है और ये कितनी बार विजिट हुआ है सिर्फ एक बार विजिट हुआ अभी जस्ट मैंने इसको विजिट किया तो ये हो गया उसका फ्रीक्वेंसी ऑफ विजिट ठीक है तो देखो इससे आपको क्या मिल जाएगा नोड और उसकी फ्रीक्वेंसी ऑफ विजिट भी मिल जाएगी ये इंफॉर्मेशन भी आप शोर कर सकते हो और ये इंफॉर्मेशन स्टोर करके आप डाइक्स में भी सॉल्व कर सकते थे कि कितनी बार वो विजिट हुआ है ठीक है तो यहां पर मुझे दो चीजें मिली कि नोड मेरा कौन है वन है और इसका कितना फ्रीक्वेंसी है फ्रीक्वेंसी ऑफ विजिट कितना एक ही एक ही बार विजिट हुआ है ये नोड है ना ठीक है तो अब आगे बढ़ते हैं देखते हैं कि इस नोड का अभी हम ग्रीन में है ना क्योंकि देखो हमारा टाइम पास जो है वो जीरो है अभी राइट टाइम पास जीरो है और य नोड एक ही बार विजिट हुआ देखो फ्रीक्वेंसी वन है तो ओबवियस सी बात है इसका मैंने यह निकाल लिया d10 d1 1 तो कितना मिला जीरो मिला टाइम पास जीरो है अगर ये दो बार विजिट हुआ होता तो तो ओबवियसली बात है मैं d2 वाला वैल्यू निकालता क्योंकि ये तो मिनिमम वैल्यू अपडेट हो रखा होगा दोबारा उसको अपडेट करने की जरूरत भी नहीं है ठीक है यहां तक क्लियर है ओके तो मैंने d1 ऑफ नोड निकाला तो रो मिला मुझे टाइम पास रो है मतलब अभी आप ग्रीन पर हो है ना तो आप नॉर्मली अपने नेबर पे चले जाओ तो वन के नेबर पर आप गए ठीक है तो वन का नेबर फोर है तो पहले आप ये देखलो देख लो कि d1 में फर का वैल्यू अपडेटेड है क्या देखो अपडेटेड नहीं है इनफिनिटी है तो ओबवियस बात है आपका फर्ज बनता है कि आप उसको अपडेट करो तो अभी टाइम पास कितना था रो था 0 + 3 करोगे ठीक है तो ओबवियस यहां पर थ्री हो जाएगा राइट और यहां पर आपको डाल देना चाहिए था नेबर कौन है फोर है और कितना विजिट है उसका बस पहला बार विजिट किया मैंने अभी फोर को पहला बार विजिट करने का मतलब क्या है कि d2 अभी अपडेटेड नहीं होगा फोर के लिए सही बात है देखो अपडेटेड नहीं है इंफिनिटी है वो यहां तक क्लियर है ओके ठीक है इसके बाद एक और नेबर कौन है थ्री है इसका नेबर ठीक है इसका नेबर थ्री है थ्री अभी इंफिनिटी है तो यस बात है यहां पर भी मैंने थ्री अपडेट कर दिया और यहां पर मैंने डाल दिया कि इसका जो नेक्स्ट नेबर था वो थ्री था और उसको भी एक ही पर विजिट किया गया ओके यहां तक क्लियर है ठीक है अब यही दो नेबर था अब मैं आगे बढ़ता हूं इसका पहला वाले को पॉप किया नोड फोर है फ्रीक्वेंसी वन है राइट तो देखो ध्यान देना यहां पर कि यहां पर फोर की फ्रीक्वेंसी जो है वो वन है मतलब एक ही बार विजिट किया गया है इसको राइट तो हम लोग क्या करेंगे इसका अ ये d1 ऑफ मतलब डिस्टेंस निकालेंगे कि भाई पहली एक ही बार विजिट किया गया तो इसका डिस्टेंस निकाल रहे हैं d1 4 कितना मिला तीन मिल गया राइट ठीक है अब मैंने कि टाइम पास चौथे नोड में पहुंचने में कितना टाइम पास हो चुका होगा तीन पास हो चुका होगा ये रहा डीवन ऑफ फोर निकाला ना मैंने तीन तो टाइम पास कितना हुआ वो मैं आराम से यहां से निकाल पा रहा हूं थ ठीक है ओके अब जब थ्री हो गया है तो मैं देख लेता हूं कि भाई क्या अभी भी मैं ग्रीन पर ही हूं हां ग्रीन पर ह ओबवियस सी बात है ग्रीन ही सिग्नल पर हो तो तुरंत भागते हैं फोर का नेबर कौन है फोर का नेबर फ दिख रहा है मुझे और थ्री भी दिख रहा है मुझे है ना तो फोर का नेबर पहले कर देखते हैं तो टाइम पास तीन था और उसमें तीन जोड़ेंगे तो छ हो जाएगा यानी कि पाच पर पहुंचने में मुझे छ लगेगा टाइम ठीक है तो छ अपडेट कर दिया मैंने और यहां पर मैं डाल भी देता हूं कि फ कमा यहां पर वन डालेंगे क्यों क्योंकि फाइव की मैंने एंट्री अभी d1 में करी है मतलब पहली बार य विजिट हुआ है सिर्फ ठीक है सिमिलरली फोर का एक और नेबर है फोर का नेबर है थ्री राइट तो अब फोर का नेबर थ्री है तो थ में जाने में मुझे कितना टाइम लगेगा टाइम पास ऑलरेडी तीन था ी में जाने में 3 प् 3 दैट इज 6 लगेगा राइट तो पहले मैं d1 में देखूंगा कि तीन पर पहुंचने में कितना वैल्यू दे रखा है ऑलरेडी तीन यहां पर है तो मैं इसको अपडेट नहीं करूंगा d2 पर देखूंगा कि यहां पर छह है तो ओबवियस मैं यहां पर छह डाल दूंगा ठीक है और जब छह मैंने डाला है तो मैं यहां पर q में क्या एंट्री करूंगा देखो तो अ नोड क्या है छह है और इसकी दूसरी विजिट है ये अ नहीं नोड मेरा कौन सा है नोड मेरा थ्री है सॉरी इसका विजिट यह दूसरा फ्रीक्वेंसी दो है क्यों क्योंकि मैंने अभी इसको d2 में डाला है मतलब इसका ये सेकंड विजिट है पहला विजिट में मैंने इसका थ अपडेट किया था और दूसरे विजिट में मैंने इसका डिस्टेंस सिक्स अपडेट किया ठीक है मतलब इसकी फ्रीक्वेंसी दो हो चुकी है इसलिए मैंने क में इसकी फ्रीक्वेंसी देखो दो लिखी है ओके अब इसके बाद आगे बढ़ते हैं इसके बाद फोर का और कोई नेबर है नहीं तो मैंने इसको हटा दिया अब बाकी आगे देखते हैं 3 व है राइट 3 व इसका मतलब क्या हुआ कि थ की फ्रीक्वेंसी वन है एक ही बार विजिट हुआ है तो यस बात है थ टाइम पास्ड में थ का लूगा तो d1 ऑफ 3 दैट इज तीन मिला थ्र का नेबर कौन है ्र का नेबर एक वन है और थ का नेबर एक 4 है राइट ठीक है तो ्र से अगर वन जाना हुआ तो कितना टाइम लगेगा टाइम पास ऑलरेडी तीन है अभी भी आप ग्रीन सिग्नल पर हो तो 3 प् 3 करके आप छ करके वन पर जा सकते हो बट वन पर देखो ऑलरेडी वैल्यू स्टोर्ड है d1 में बट d2 में स्टोर्ड नहीं है तो d2 में आप सिक्स डाल सकते हो सिक्स डाल दिया आपने अब देखो ये सेकंड मिनिमम वैल्यू है राइट तो q में हम लोग डाल देंगे कि वन पे पहुंचने का सेकंड मिनिमम वैल्यू मुझे मिल चुका है ठीक है तो वन पर यह सेकंड विजिट है फ्रीक्वेंसी देखो मैंने दो डाल दिया है q में है ना क्योंकि d2 में मैंने डाला है इसकी एंट्री सिमिलरली थी का नेक्स्ट नेबर कौन है फोर है तो 3 से फर जाने पे कितना टाइम लगेगा वो देखते हैं ऑलरेडी टाइम पास तीन था और तीन करेंगे तो छ लगेगा बट फोर पे ऑलरेडी मैंने वैल्यू यहां स्टोर कर रखी है d1 में तो d2 में जब डालेंगे तो यस सी बात है यहां पर छ डालेंगे और यहां पर मैं बता दूंगा q को कि नोड नंबर फोर का फ्रीक्वेंसी अब दो चुका है मतलब दो दूसरी बार भी हमने इसको विजिट कर रखा है ठीक है अब आते हैं 5 व पर तो आप इस 5 व को प्रोसेस करोगे उसके बाद टू को प्रोसेस करोगे एंड टू को प्रोसेस करोगे इसी तरह फिर लास्ट में देखो 4 2 को प्रोसेस करोगे ठीक है तो अब देखो यहां पर 4 2 जो है फोर का नेबर फ है बट इस फोर को अगर आप ध्यान दोगे इस 4 2 को मतलब नोड जब आप यहां पहुंचो के नोड फोर है और इसका फ्रीक्वेंसी देखो दो है है ना फ्रीक्वेंसी जब दो है इसका मत मत क्या है कि मुझे d2 वाला टाइम निकालना पड़ेगा तो d2 ऑफ 4 देखते हैं 6 है ठीक है तो इस बार टाइम पास कितना हो जाएगा टाइम पास्ड इल ट 6 होगा इस बार ठीक है अब सिक्स टाइम पास्ड है तो मतलब अभी आप 6 बाय चेंज करोगे तो 6/5 ट इज 1 पॉइंट समथिंग आएगा ये एक ऑड नंबर है मतलब अभी आप रेड सिग्नल पर हो तो नेक्स्ट ग्रीन सिग्नल कब मिलेगा कैसे निकालो 10 हो जाएगा ना वो ठीक है तो दव सेकंड पर आप ग्रीन सिग्नल पर ग्रीन सिगनल आ चुका होगा और आप फोर पर ख खड़े हो गए तब के टाइम ठीक है और आप फोर से जब आप अपने नेबर पर जाओगे फाइव के पास तो कितना लग जाएगा 10 प् 3 दैट इज 13 ओके और आप ध्यान दोगे कि अच्छा फ पर पहुंचने का मिनिमम वैल्यू छ है ऑलरेडी जो अपडेटेड है लेकिन ट अपडेटेड नहीं है तो मैंने आपकी इसको अपडेट कर दोगे 13 को 13 प अपडेट कर दिया अब देखो फ प पहुंचने का सेकंड मिनिमम वैल्यू मिल चुका है आपको ठीक है तो ओबवियस है आप अपने q में डालोगे इसको कि फ प पहुंच चुका हूं मैं और सिंस मैंने d 2 पर डाला है वैल्यू इस बार तो इसकी फ्रीक्वेंसी दो हो चुकी है जब फ्यूचर में आप 52 को पॉप करोगे ना तो आप देखोगे कि फाइव जो है मेरा डेस्टिनेशन नोड है और इसकी फ्रीक्वेंसी दो है मतलब सेकंड टाइम मैंने इसको विजिट कर रखा है मतलब d2 में पक्का इसकी वैल्यू स्टोर्ड होगी स्टोर्ड है तो मतलब वही मेरा सेकंड मिनिमम वैल्यू और 13 इसका आंसर होगा यहां तक क्लियर है तो देखा तो डाा वाली ही चीज मैंने दोबारा रिपीट करी है इसमें ठीक है बट स्टिल ड्राय रन वाज इंपोर्टेंट इसलिए मैंने ड्रा रन किया है सेम कोड को जल्दी से लीड कोड करते हैं और इसको फिनिश करते हैं तो चलो अब इसका बीएफएस का कोड लिख देते हैं इसमें सब कुछ सेम होगा ग्राफ मैंने यहां पर बना दिया है d1 d2 ले लिया है बस प्रायोरिटी क्य हमें अब नहीं लेना है है ना तो प्रायोरिटी क्य मैं यहां पर हटा देता हूं प्रायोरिटी क की जगह हमें क्या लेना था सिंपल q लेना था और यह क्यू ऑफ पेयर होगा इसका नाम q रख देते हैं ठीक है और यहां पर क्य डॉट पुश में याद करो दो चीजें स्टोर करते थे कि मेरा नोड कौन सा है नोड अभी वन है स्टार्टिंग में और कितनी बार विजिट हुआ है राइट मतलब नोड और उसकी फ्रीक्वेंसी कितनी बार विजिट हुई है तो वनव डाला मतलब ये वाला नोड अभी एक बार विजिट हुआ है ठीक है और एक बार विजिट हुआ तो d1 में मैंने इसकी डिस्टेंस टाइम स्टोर कर दिया कि नोड नंबर वन के लिए जीरो टाइम लगेगा ओबवियस सी बात है ठीक है ओके तो अब हम लोग आ जाते हैं अपने बीएफएस वाले कोड पे तो बीएफएस वाला कोड को यहां पर चेंज कर देते हैं यहां पर p क की जगह q एमटी हो जाएगा ठीक है और ऑटो नोड फ्रीक्वेंसी यहां पर ये टाइम पास तो अब नहीं होगा यहां पर यहां पर नोड है और यह उसकी फ्रीक्वेंसी निकल कर आएगी ठीक है प क पॉप कर दिया मैंने और यहां पर टाइम पास निकाल लेते हैं अब हमें टाइम पास भी निकालना होगा ना इंट टाइम पास्ट इ इक्वल टू अभी मैंने क्या बोला था कि अगर वह एक बार ही सिर्फ विजिट हुआ है वो नोड ठीक है तो यस सी बात है उसका डीटू में उसकी वैल्यू नहीं होगी व में उसकी वैल्यू होगी तोव ऑफ दैट नोड ठीक है और अगर ऐसा नहीं है दूसरी बार भी विजिट हो चुका है तो d2 ऑफ नोड निकालेंगे यहां तक क्लियर है ठीक है और यहां पर हम मैंने क्या बोला था चेक कर लेंगे कि अगर नोड इ इल = n है और d2n नॉ इक्वल टू एंट मैक्स है तो d2n रिटर्न कर देंगे तो ये लाइन अभी भी वही रहेगा इसमें कोई चेंज नहीं है है ना जो डाा में था वो यहां पर भी है ठीक है ये भी चेंज नहीं होगा इंट डिवीजन डिवीजन परसेंटाइल टू सब कुछ सेम है नेबर पे रेट मार रहे ये भी सेम है इसको ये थोड़ा सिंपल हो जाएगा हमारा इसको हटा देते हैं यहां पर बस हमें ये चेक करना है कि एक सेकंड किव का जो नेबर का वैल्यू है अगर वह इंट मैक्स हुआ मतलब अभी तक उसकी वैल्यू मैंने अपडेट नहीं की है राइट तो यस बात है मैं डी व ऑफ नेबर में डाल दूंगा कि भाई टाइम पास्ड प्लस टाइम इतना लगेगा नेबर में पहुंचने में ठीक है और क्य में पुश कर दूंगा क्योंकि य नेवर पहली बार विजिट हुआ है देखो क्योंकि इसकी वैल्यू इंट मैक्स थी अभी य पहली बार विजिट हुआ है तो यहां पर मैं डाल देता हूं नोड कौन सा है नेबर है और इसकी फ्रीक्वेंसी वन है एल्स इफ अगर d2 ऑफ नेबर अगर वह भी फिल नहीं हुआ है इंट मैक्स हुआ बट ये इंश्योर करना है कि d1 ऑफ नेबर की वैल्यू ये सेम नहीं होनी चाहिए राइट टाइम पास्ड प्लस टाइम तभी जाके हम d2 ऑफ नेबर की वैल्यू ये सेट कर सकते हैं टाइम पास्ड प्लस टाइम जैसे ही सेट किया q में पुश करेंगे कड पुश अ मेरा नेबर यह है और यह देखो दूसरी बार विजिट हुआ क्योंकि मैंने इसको d2 में पुश किया तो ये दूसरी बार का विजिट है इसका ठीक है इसको सबमिट करके देखते हैं वी शुड बी एबल टू पास ऑल द टस केसेस अब ध्यान दो हम इस ग्राफ में हमने नॉर्मल बीएफएस ट्रैवर्सल किया है राइट यहां पर p क के जगह लाइन नंबर कहां पर है 22 यहां पर p क नहीं होगा q होगा q डॉट और यहां पर टॉप नहीं होगा फ्रंट होगा क्योंकि ये कू है हमारा राइट और यहां पर भी q पॉप होगा लेट्स सी और नॉर्मल बीएफएस ट्रैवर्सल है तो टाइम कंपलेक्सिटी o ऑफ v + e होगा जहां पर v नंबर ऑफ वर्टिसेज है e नंबर ऑफ एजेस है और स्पेस कंपलीसिटी सेम होगा v ऑफ v+ e जो मैंने यहां पर लिया और यहां पर ओ और ओ ठीक है सी यू गदर नेक्स्ट वीडियो थैंक यू