पायथन में किनारे की लंबाई सीमित पथों के अस्तित्व की जाँच करने का कार्यक्रम

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

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

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

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

• जनक :=0 से n तक की सूची

• रैंक :=आकार n+1 की सूची और 0 से भरें

• फ़ंक्शन ढूंढें() को परिभाषित करें। यह माता-पिता को ले जाएगा, x

• यदि माता-पिता [x] x के समान है, तो

  • वापसी x

• माता-पिता [x]:=ढूंढें (माता-पिता, माता-पिता [x])

• माता-पिता को लौटाएं[x]

• एक फ़ंक्शन यूनियन () को परिभाषित करें। यह माता-पिता, a, b को लेगा

• ए:=ढूंढें (माता-पिता, ए)

• बी:=ढूंढें (माता-पिता, बी)

• अगर a, b के समान है, तो

  • वापसी

• अगर रैंक [ए] <रैंक [बी], तो

  • माता-पिता [ए]:=बी

• अन्यथा जब रैंक [ए]> रैंक [बी], तब

  • माता-पिता [बी] :=ए

• अन्यथा,

  • माता-पिता [बी] :=ए

  • रैंक [ए]:=रैंक [ए] + 1

• मुख्य विधि से निम्न कार्य करें -

• वजन मापदंडों के आधार पर किनारे की सूची को क्रमबद्ध करें

• res :=प्रश्नों की संख्या वाली एक सरणी और 0 से भरें

• क्वेरीज़:=प्रत्येक इंडेक्स i के लिए जोड़ी (i, ch) की एक सूची और क्वेरी से मान ch

• सीमा मापदंडों के आधार पर प्रश्नों को क्रमबद्ध करें

• इंडस्ट्रीज़:=0

• प्रत्येक अनुक्रमणिका के लिए मैं प्रश्नों में तीन गुना (ए, बी, डब्ल्यू), करता हूं

  • जबकि ind

    • यूनियन (पैरेंट, एजलिस्ट [इंड, 0])

    • इंडस्ट्रीज़:=इंडस्ट्रीज़ + 1

  • res[i] :=find(parent, a) find(parent, b)

    . के समान है

• रिटर्न रेस

उदाहरण

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

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]