पायथन में एक जंगल को जोड़ने का कार्यक्रम

मान लीजिए कि हमारे पास आसन्न सूची के रूप में ग्राफ़ हैं। यह ग्राफ वास्तव में असंबद्ध वृक्षों का एक समूह है। हमें जंगल में एक निश्चित संख्या में किनारों को जोड़ना होगा ताकि वह एक ही पेड़ बन जाए। हमें किन्हीं दो नोड्स के बीच सबसे लंबे पथ की न्यूनतम संभव दूरी को वापस करना होगा। तो, अगर इनपुट पसंद है

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

हम किनारे 0 −> 5 जोड़ सकते हैं। फिर, सबसे लंबा पथ 3 −> 1 −> 0 −> 5 −> 7 या 4 −> 1 −> 0 −> 5 −> 7 में से कोई भी हो सकता है; और ये रास्ते भी उलटे दिशा वाले। तो हम दूरी 4 लौटाते हैं।

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

• देखा :=एक नया सेट

• डीआईसी:=ग्राफ

• एक फ़ंक्शन ट्रीडेप्थ () को परिभाषित करें। यह नोड लेगा।

  • रिट:=0

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

    • देखे गए सेट में एक नोड जोड़ें

    • best2 :=एक खाली न्यूनतम हीप संरचना

    • डीआईसी [नोड] में प्रत्येक एनएक्सटी के लिए, करें

      • अगर नेक्स्ट पैरेंट के समान नहीं है, तो

        • push(dfs1(nxt, node) + 1) best2 में

      • अगर लेन(सर्वश्रेष्ठ2)> 2, तो

        • ढेर से पॉप(सर्वश्रेष्ठ2)

      • अगर best2 खाली है, तो

        • वापसी 0

      • ret :=अधिकतम रिट, best2 के सभी तत्वों का योग

      • अधिकतम 2 लौटाएं

    • dfs1(नोड, नल)

    • वापसी रिट

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

• रिट:=0, ऑप्ट:=एक नई सूची, गाओ:=0

  • नोड के लिए 0 से ग्राफ़ के आकार की सीमा में, करें

    • यदि नोड दृश्य में मौजूद है, तो

      • अगले पुनरावृत्ति के लिए जाएं

    • रेस:=ट्रीडेप्थ (नोड)

    • गाना :=अधिकतम गाना, रेस

    • ऑप्ट के अंत में (res / 2) की सीलिंग डालें

  • यदि ऑप्ट का आकार <=1 है, तो

    • वापसी गाना

  • एमएक्स:=अधिकतम ऑप्ट

  • मैं के लिए 0 से लेकर ऑप्ट के आकार तक, करें

    • अगर ऑप्ट [i] एमएक्स के समान है, तो

      • ऑप्ट [i] :=ऑप्ट [i] − 1

      • लूप से बाहर आएं

  • मैं के लिए 0 से लेकर ऑप्ट के आकार तक, करें

    • ऑप्ट [i] :=ऑप्ट [i] + 1

  • high2 :=ऑप्ट से सबसे बड़े 2 तत्व।

  • अधिकतम योग (उच्च 2) लौटाएं और गाएं

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

उदाहरण

import heapq, math
class Solution:
   def solve(self, graph):
      seen = set()
      dic = graph
      def treeDepth(node):
         self.ret = 0
         def dfs1(node, parent):
            seen.add(node)
            best2 = []
            for nxt in dic[node]:
               if nxt != parent:
                  heapq.heappush(best2, dfs1(nxt, node) + 1)
                  if len(best2) > 2:
                     heapq.heappop(best2)
            if not best2:
               return 0
            self.ret = max(self.ret, sum(best2))
            return max(best2)
         dfs1(node, None)
         return self.ret
      ret = 0
      opt = []
      sing = 0
      for node in range(len(graph)):
         if node in seen:
            continue
         res = treeDepth(node)
         sing = max(sing, res)
         opt.append(int(math.ceil(res / 2)))
      if len(opt) <= 1:
         return sing
      mx = max(opt)
      for i in range(len(opt)):
         if opt[i] == mx:
            opt[i] −= 1
            break
         for i in range(len(opt)):
            opt[i] += 1
         high2 = heapq.nlargest(2, opt)
         return max(sum(high2), sing)
ob = Solution()
graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]
print(ob.solve(graph))

इनपुट

graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]

आउटपुट

4