पायथन में सबसे लंबी संभावित छड़ी की लंबाई ढूंढने का प्रोग्राम

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

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

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

• एक फ़ंक्शन dfs() परिभाषित करें। यह node, edge_idx, और एक सेट visited लेगा
• यदि edge_idx null नहीं है, तो
  • यदि edge_idx visited है, तो
    • 0 लौटाएं
  • edge_idx को visited के रूप में मार्क करें
  • res := 0
  • g[node] में प्रत्येक e_idx के लिए, करें
    • n_node := sticks[e_idx, 0] जब sticks[e_idx, 1] node के समान है अन्यथा sticks[e_idx, 1]
    • res := res और 1 + dfs(n_node, e_idx, visited) का अधिकतम
  • यदि edge_idx नॉन-ज़ीरो है, तो
    • visited से edge_idx हटाएं
  • res लौटाएं
• मुख्य विधि से निम्न करें:
• sticks := सभी s के लिए sticks में (s[0], s[1]) की एक सूची
• vertices := एक नया सेट
• g := एक खाली मैप
• प्रत्येक इंडेक्स i और edge के लिए sticks में, करें
  • i को g[edge[0]] में डालें
  • i को g[edge[1]] में डालें
  • edge[0] और edge[1] को vertices में डालें
• res := 0
• vertices में प्रत्येक v के लिए, करें
  • res := res और dfs(v, null, और खाली सेट) का अधिकतम
• res - 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