Competitive Programming Academy · पाठ

Rank और Components के अनुसार Union

trees को flat रखें और groups गिनें

पाठ 2, कुल 4 में से13 चरण

Rank और Components के अनुसार Union, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

union को सरलता से भी किया जा सकता है

साधारण union बस एक मूल को दूसरे के नीचे रख देता है। लापरवाही से ऐसा करने पर लंबा और धीमा वृक्ष बन सकता है, इसलिए हमें मूलों को मिलाने का बेहतर तरीका चाहिए।

मुख्य विचार

रैंक-आधारित union हमेशा छोटे वृक्ष को बड़े वृक्ष के नीचे जोड़ता है। वृक्षों को उथला रखने से बाद में होने वाला हर find तेज़ हो जाता है। 📏

रैंक का अर्थ

रैंक वृक्ष की ऊँचाई का एक अनुमान है। हर तत्व रैंक 0 से शुरू होता है, क्योंकि एकल नोड के नीचे कोई गहराई नहीं होती।

rank = [0] * n

छोटे को बड़े से जोड़िए

दोनों मूलों की रैंक की तुलना कीजिए। छोटी रैंक वाला मूल बालक बन जाता है, ताकि संयुक्त वृक्ष यथासंभव चपटा रहे।

if rank[ra] < rank[rb]:
    parent[ra] = rb

बराबरी पर रैंक बढ़ती है

जब दोनों मूलों की रैंक समान हो, तो किसी एक को नया मूल चुनकर उसकी रैंक एक बढ़ा दीजिए, क्योंकि वृक्ष एक स्तर ऊँचा हो गया है।

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

आकार-आधारित union

एक लोकप्रिय विकल्प आकार-आधारित union है: छोटे समुच्चय को बड़े समुच्चय के नीचे जोड़िए। यह भी उतना ही प्रभावी है और समूहों के आकार निःशुल्क उपलब्ध कराता है।

घटकों की गिनती

संख्या को n से शुरू कीजिए, क्योंकि हर तत्व अपना अलग समूह है। हर सफल union दो समूहों को एक में जोड़ता है, इसलिए संख्या में एक घटाइए।

components = n

निष्क्रिय union छोड़ दीजिए

यदि दो तत्व पहले से एक ही मूल साझा करते हैं, तो union कुछ नहीं करता। संख्या तभी घटाइए जब उनके मूल वास्तव में अलग हों।

if find(a) != find(b):
    union(a, b)
    components -= 1

रैंक और संपीड़न

रैंक-आधारित union को पथ संपीड़न के साथ मिलाने पर DSU व्युत्क्रम-एकरमैन समय में चलता है, जो किसी भी वास्तविक इनपुट के लिए लगभग स्थिर माना जाता है। ⚡

आवश्यकता पर समूह का आकार

आकार-आधारित union से आप तुरंत पता लगा सकते हैं कि कोई समूह कितना बड़ा है: बस उस तत्व के मूल में रखा हुआ आकार पढ़िए।

group = size[find(x)]

यह कहाँ उपयोगी है

घटकों की गिनती से संयोजन संचालनों की शृंखला के बाद मित्र-मंडलियों की संख्या या जुड़े हुए क्षेत्रों की संख्या जैसे पारंपरिक प्रश्नों के उत्तर मिलते हैं। 🌐

त्वरित जाँच

सोचिए कि घटकों का काउंटर कैसे बदलता है।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावृत्ति

आपने वृक्षों को समतल रखने के लिए रैंक के आधार पर संयोजन करना और घटकों की संख्या व समूहों के आकार पर नज़र रखना सीखा। DSU अब बहुत तेज़ है! 🎉

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Rank और Components के अनुसार Union” पाठ निःशुल्क है?

हाँ—“Rank और Components के अनुसार Union” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Rank और Components के अनुसार Union” में मैं क्या सीखूँगा?

trees को flat रखें और groups गिनें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“Rank और Components के अनुसार Union” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← Competitive Programming Academy पर वापस जाएँ