सभी चुनौतियाँ
कठिन 1 हल किया गया 100.0% स्वीकृति

न्यूनतम नेटवर्क कनेक्शन लागत

ऐसे अविनिर्दिष्ट लिंक चुनें ताकि प्रत्येक शीर्षक (vertex) अन्य सभी शीर्षकों तक पहुँच सके, और कुल लागत न्यूनतम हो।

आप क्या सीखेंगे

  • क्रुस्कल एल्गोरिदम से ग्राफ़ को सस्ते में जोड़ना
  • डिसजॉइंट सेट से चक्र पहचानना
  • बताना कि ग्राफ़ कब नहीं जुड़ सकता

समस्या

ऐसे अविनिर्दिष्ट लिंक चुनें ताकि प्रत्येक शीर्षक (vertex) अन्य सभी शीर्षकों तक पहुँच सके, और कुल लागत न्यूनतम हो। कोई भी लिंक दोनों दिशाओं में इस्तेमाल किया जा सकता है। यदि उपलब्ध लिंक पूरे नेटवर्क को नहीं जोड़ सकते, तो −1 लौटाएँ। आपको चुने गए लिंक लौटाने की आवश्यकता नहीं है।

minimum_network_connection_cost(vertices, links) को लागू करें।

इनपुट

vertices: नेटवर्क में शीर्षकों (vertices) की संख्या।

links: उपलब्ध लिंक [u, v, cost] के रूप में।

आउटपुट

न्यूनतम कुल लागत लौटाएँ, यदि असंभव हो तो −1 लौटाएँ, या एक-शीर्षक नेटवर्क के लिए 0 लौटाएँ।

सीमाएँ

1 ≤ vertices ≤ 100,000। 0…200,000 लिंक; एंडपॉइंट्स 1…vertices में विशिष्ट शीर्षक हैं। लागत 1…1,000,000,000 के बीच है। समान एंडपॉइंट्स के लिए एक से अधिक लिंक (parallel links) की अनुमति है। कुल मान signed 64-bit में समा जाता है।

उदाहरण

उदाहरण 1
इनपुट:
vertices = 3
links = [
    [1, 2, 4],
    [2, 3, 2],
    [1, 3, 7]
]

अपेक्षित आउटपुट:
expected = 6
इनपुट:
long long vertices = 3;
std::vector<std::vector<long long>> links = {
    {1, 2, 4},
    {2, 3, 2},
    {1, 3, 7}
};

अपेक्षित आउटपुट:
long long expected = 6;
इनपुट:
long vertices = 3;
long[][] links = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 2},
    new long[] {1, 3, 7}
};

अपेक्षित आउटपुट:
long expected = 6;

व्याख्या

सभी तीन शीर्षकों को जोड़ने के लिए लागत 4 और 2 वाले लिंक चुनें। इनकी कुल लागत 6 है; लागत 7 वाला लिंक आवश्यक नहीं है।

उदाहरण 2
इनपुट:
vertices = 3
links = [
    [1, 2, 4]
]

अपेक्षित आउटपुट:
expected = -1
इनपुट:
long long vertices = 3;
std::vector<std::vector<long long>> links = {
    {1, 2, 4}
};

अपेक्षित आउटपुट:
long long expected = -1;
इनपुट:
long vertices = 3;
long[][] links = new long[][] {
    new long[] {1, 2, 4}
};

अपेक्षित आउटपुट:
long expected = -1;

व्याख्या

शीर्षक 3 का कोई कनेक्शन नहीं है। कोई भी चयन पूरे नेटवर्क को नहीं जोड़ सकता।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

तुम्हें links का ऐसा सबसे सस्ता set चाहिए जो फिर भी हर vertex को connected रखे, इसलिए spanning tree सोचो।

संकेत 2

Greedily सबसे सस्ता ऐसा link जोड़ो जो cycle न बनाए, या union-find structure से components बढ़ाओ।

संकेत 3

अगर vertices minus one से कम usable links graph को connect करें, तो answer impossible है।

अपेक्षित जटिलता

समय O(links log links), अतिरिक्त स्थान O(vertices + links)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 848 ms - 5/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।