पायथन में सबसे लंबी संभव छड़ी की लंबाई खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास पूर्णांक स्टिक्स की एक सूची है। यहां सूची में प्रत्येक तत्व दो सिरों वाली एक छड़ी का प्रतिनिधित्व करता है, ये मान 1 और 6 के बीच हैं। ये प्रत्येक छोर का प्रतिनिधित्व कर रहे हैं। हम दो छड़ियों को एक साथ जोड़ सकते हैं यदि उनका कोई सिरा समान हो। परिणामी छड़ी के सिरे बचे हुए सिरे होंगे और इसकी लंबाई बढ़ाई जाएगी। हमें सबसे लंबी छड़ी की लंबाई ज्ञात करनी होगी।

इसलिए, यदि इनपुट स्टिक्स की तरह है =[ [2, 3], [2, 4], [3, 5], [6, 6]], तो आउटपुट 3 होगा, जैसा कि हम [2, 3] कनेक्ट कर सकते हैं ] और [2, 4] [3, 4] प्राप्त करने के लिए, जिसे हम [3, 5] से जोड़कर [4, 5] प्राप्त कर सकते हैं।

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

• फ़ंक्शन को परिभाषित करें dfs() । यह नोड, edge_idx, और एक सेट का दौरा करेगा

• अगर edge_idx रिक्त नहीं है, तो

  • अगर edge_idx का दौरा किया जाता है, तो

    • वापसी 0

  • Edge_idx को विज़िट किया गया के रूप में चिह्नित करें

  • रेस :=0

  • g[नोड] में प्रत्येक e_idx के लिए, करें

    • n_node :=चिपक जाती है[e_idx, 0] जब चिपक जाती है[e_idx, 1] नोड के समान होती है अन्यथा चिपक जाती है[e_idx, 1]

    • रेस :=अधिकतम रेस और 1 + dfs(n_node, e_idx, विज़िट किया गया)

  • अगर edge_idx गैर-शून्य है, तो

    • देखे गए से edge_idx हटाएं

  • रिटर्न रेस

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

• स्टिक्स :=स्टिक्स में सभी s के लिए एक सूची (s[0], s[1])

• कोने :=एक नया सेट

• g :=एक खाली नक्शा

• प्रत्येक अनुक्रमणिका i और स्टिक्स में किनारे के लिए, करें

  • i को g[edge[0]]

    . में डालें

  • i को g [एज [1]]

    में डालें

  • किनारे [0] और किनारे [1] को कोने में डालें

• रेस :=0

• कोने में प्रत्येक v के लिए, करें

  • रेस:=अधिकतम रेस और डीएफएस (वी, नल, और खाली सेट)

• वापसी रेस - 1

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

उदाहरण

from collections import defaultdict

class Solution:
   def solve(self, sticks):
      def dfs(node, edge_idx, visited):
         if edge_idx is not None:
            if edge_idx in visited:
               return 0
            visited.add(edge_idx)
         res = 0
         for e_idx in g[node]:
            n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
            res = max(res, 1 + dfs(n_node, e_idx, visited))
         if edge_idx:
            visited.remove(edge_idx)
         return res

      sticks = [(s[0], s[1]) for s in sticks]
      vertices = set()
      g = defaultdict(set)
      for i, edge in enumerate(sticks):
         g[edge[0]].add(i)
         g[edge[1]].add(i)
         vertices.add(edge[0])
         vertices.add(edge[1])
      res = 0
      for v in vertices:
         res = max(res, dfs(v, None, set()))
      return res - 1

ob = Solution()
sticks = [
   [2, 3],
   [2, 4],
   [3, 5],
   [6, 6]
]
print(ob.solve(sticks))

इनपुट

sticks = [ [2, 3], [2, 4], [3, 5], [6, 6] ]

आउटपुट

3