यह पता लगाने के लिए कार्यक्रम कि क्या अप्रत्यक्ष ग्राफ में एक शीर्ष का पायथन में कम लागत वाला पथ है

मान लीजिए, हमें एक भारित, अप्रत्यक्ष ग्राफ दिया गया है। हमें एक फ़ंक्शन क्वेरी को कार्यान्वित करना होगा जो इनपुट के रूप में दो शिखर और लागत 'सीमा' लेता है और जांचता है कि इनपुट के रूप में दी गई लागत से कम लागत पथ मौजूद है या नहीं। यदि कोई पथ मौजूद है या अन्यथा, हम सही लौटते हैं, तो हम झूठे लौटते हैं।

तो, अगर इनपुट पसंद है

और प्रश्न हैं (0, 2, 10), (3, 1, 30), (4, 3, 30)।

तो आउटपुट होगा

False
True
True

पहली क्वेरी का परिणाम गलत है क्योंकि लागत 10 के शीर्ष 0 से 2 के बीच कोई पथ नहीं है।

दूसरी क्वेरी का परिणाम सही है क्योंकि लागत 10 के शीर्ष 3 से 1 के बीच एक पथ है, जो 30 से कम है।

तीसरी क्वेरी का परिणाम सही है क्योंकि लागत 30 के शीर्ष 4 से 3 के बीच एक पथ है, जो 30 के बराबर है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• वज़न :=ग्राफ़ में अलग-अलग वज़न वाली एक सूची

• कनेक्शन :=वज़न के लिए कनेक्शन वाली सूची

• फ़ंक्शन क्वेरी () को परिभाषित करें। यह p, q, सीमा लेगा

  • अनुक्रमणिका :=भार में स्थिति यहाँ सीमा को क्रमबद्ध क्रम को बनाए रखने के बाईं ओर डाला जा सकता है

  • यदि अनुक्रमणिका 0 के समान है, तो

    • झूठी वापसी

  • यदि कनेक्शन [इंडेक्स -1, पी] कनेक्शन के समान है [इंडेक्स -1, क्यू]

उदाहरण

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

import bisect
class Solution(object):

   def __init__(self, n, edgeList):
      def find(node):
         if parent[node]!=node:
            parent[node] = find(parent[node])
         return parent[node]

      def union(x,y):
         parent[find(y)] = find(x)
         return

      parent = {i:i for i in range(n)}
      edgeList.sort(key = lambda x:x[2])
      self.connections = []
      self.weights = []
      for index,(i,j,weight) in enumerate(edgeList):
         union(i,j)
         if index!=len(edgeList)-1 and weight == edgeList[index+1][2]:
            continue
         self.weights.append(weight)
         self.connections.append([find(i) for i in parent])


   def query(self, p, q, limit):
      index = bisect.bisect_left(self.weights,limit)
      if index==0:
         return False
      return self.connections[index-1][p] == self.connections[index-1][q]

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))

इनपुट

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))

आउटपुट

False
True
True