हम जानते हैं कि अलग-अलग सेटों के लिए "संघ और खोज" है। http://en.wikipedia.org/wiki/Union_find"संघ और खोज" के लिए रिवर्स ऑपरेशन
लेकिन रिवर्स ऑपरेशन कैसे करें? ई किनारों से जुड़े एन नोड्स के साथ एक सेट पर विचार करें (जो वास्तव में एक ग्राफ है)। और प्रत्येक चरण में हम कुछ किनारे को हटाना चाहते हैं और जांचें कि क्या इस डिलीट ऑपरेशन में एक और डिस्जिइंट सेट है। क्या इसे "संघ और खोज" में तेजी से करना संभव है?
पी.एस इस होमवर्क नहीं है, हम छुट्टी :)
इस ऑनलाइन बढ़त विलोपन समस्या या ऑनलाइन कनेक्टिविटी समस्या के रूप में जाना जाता है। एल्गोरिदम के कुछ लिंक इस section of the Wikipedia article on graph connectivity में हैं।
तो आपका प्रश्न यह है कि Bridge को कुशलतापूर्वक कैसे पहचानें? यह रैखिक समय में किया जा सकता है (लिंक भी देखें)।
यह देखते हुए कि @ क्रिस स्पष्ट रूप से ऑपरेशन को बार-बार करना चाहता है (वह "प्रत्येक चरण में" कहता है) हम प्रत्येक चरण में पुलों का पता लगाने में अधिक कुशल हो सकते हैं। – borrible
मुझे लगता है कि यदि आप उस पुल को एल्गोरिदम ढूंढते हैं और पुलों को चिह्नित करते हैं और ध्यान दें कि जब तक कि ग्राफ में कोई किनारा नहीं जोड़ा जाता है, कोई नया पुल दिखाई नहीं दे सकता है; उस ग्राफ में मौजूद सभी पुल पुलों के रूप में बने रहते हैं क्योंकि किनारों को हटा दिया जाता है और नए पुल केवल तभी दिखाई दे सकते हैं जब आप एक किनारे को हटा दें जो पुल नहीं है; इसलिए आपको केवल दो उपग्राफों पर एल्गोरिदम को फिर से चालू करने की आवश्यकता है जो एक गैर-पुल किनारे से जुड़ा हुआ था जिसे अभी हटा दिया गया था। –
क्रॉसकल एल्गोरिदम में संघ-खोज का उपयोग किया जाता है, जो बार-बार न्यूनतम वजन का किनारा जोड़ता है जो चक्र नहीं बनाता है। एक रिवर्स विचार - जब तक यह ग्राफ को डिस्कनेक्ट नहीं करता है तब तक अधिकतम वजन के किनारों को हटाया जाता है - reverse-delete algorithm में उपयोग किया जाता है, जो प्रतीत होता है कि कुछ जटिल डेटा संरचना (विकिपीडिया देखें) का उपयोग कर सकते हैं।
अगला अच्छा लिंक, लेकिन बहुत अधिक सामान्यीकृत और वास्तव में कोई कोड देखने के लिए :( – Spinach
लिंक के लिए धन्यवाद। मैं केवल एसीएम पर खरीदने के लिए लेख पा सकता हूं। टॉपकोडर, कोई सीधा लिंक पर कोई जानकारी नहीं मिली? :) – Spinach