पायथन में एज लेंथ लिमिटेड पथ के अस्तित्व की जांच करने का प्रोग्राम

मान लीजिए हमारे पास एक अनडायरेक्टेड वेटेड ग्राफ है जिसमें n नोड्स हैं, edgeList का उपयोग करके, जहां edgeList[i] में तीन पैरामीटर (u, v, w) हैं जो दर्शाते हैं कि u से v तक एक पथ है जिसकी दूरी w है। हमारे पास एक और क्वेरी ऐरे है जहां query[i] में (p, q, lim) है। यह क्वेरी पूछ रही है कि क्या p से q तक एक पथ (सीधे या किसी अन्य नोड के माध्यम से) है जिसकी दूरी lim से कम है। हमें प्रत्येक क्वेरी के लिए True/False परिणाम रखने वाला ऐरे वापस करना है।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट [True, False, True] होगा। क्योंकि 1 से 4 जाने के लिए हम पथ 1 -> 3 -> 4 का अनुसरण कर सकते हैं जिसकी लागत 11 है, दूसरा गलत है क्योंकि हम 2 से 3 तक 3 से कम का उपयोग करके नहीं जा सकते, और तीसरा सही है क्योंकि हम 1 से 2 तक पथ 1 -> 3 -> 2 का उपयोग करके जा सकते हैं जिसकी लागत 14 है जो 15 से कम है।

हल करने के चरण

1. parent := 0 से n तक की सूची
2. rank := आकार n+1 की सूची और 0 से भरें
3. find() फ़ंक्शन परिभाषित करें। यह parent, x लेगा:
   • यदि parent[x] == x, तो x वापस करें।
   • parent[x] := find(parent, parent[x])
   • parent[x] वापस करें।
4. union() फ़ंक्शन परिभाषित करें। यह parent, a, b लेगा:
   • a := find(parent, a)
   • b := find(parent, b)
   • यदि a == b, तो वापस करें।
   • यदि rank[a] < rank[b], तो parent[a] := b
   • अन्यथा यदि rank[a] > rank[b], तो parent[b] := a
   • अन्यथा:
     • parent[b] := a
     • rank[a] := rank[a] + 1
5. मुख्य मेथड से निम्नलिखित करें:
   • edgeList को वेट पैरामीटर के आधार पर सॉर्ट करें।
   • res := क्वेरी की संख्या के साथ ऐरे और 0 से भरें
   • queries := प्रत्येक इंडेक्स i और मान ch के लिए जोड़ी (i, ch) की सूची
   • queries को लिमिट पैरामीटर के आधार पर सॉर्ट करें।
   • ind := 0
   • queries में प्रत्येक इंडेक्स i ट्रिपलेट (a, b, w) के लिए:
     • ind < len(edgeList) और edgeList[ind][2] < w तक व्हाइल लूप चलाएं:
       • union(parent, edgeList[ind][0], edgeList[ind][1])
       • ind := ind + 1
     • res[i] := find(parent, a) == find(parent, b)
   • res वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(n, edgeList, queries):
    parent = [i for i in range(n+1)]
    rank = [0 for i in range(n+1)]
    def find(parent, x):
        if parent[x] == x:
            return x
        parent[x] = find(parent, parent[x])
        return parent[x]
    def union(parent, a, b):
        a = find(parent, a)
        b = find(parent, b)
        if a == b:
            return
        if rank[a] < rank[b]:
            parent[a] = b
        elif rank[a] > rank[b]:
            parent[b] = a
        else:
            parent[b] = a
            rank[a] += 1
    edgeList.sort(key=lambda x: x[2])
    res = [0] * len(queries)
    queries = [[i, ch] for i, ch in enumerate(queries)]
    queries.sort(key=lambda x: x[1][2])
    ind = 0
    for i, (a, b, w) in queries:
        while ind < len(edgeList) and edgeList[ind][2] < w:
            union(parent, edgeList[ind][0], edgeList[ind][1])
            ind += 1
        res[i] = find(parent, a) == find(parent, b)
    return res

n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))

इनपुट

4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)], [(1,4,12),(2,3,3),(1,2,15)]

आउटपुट

[True, False, True]