程序在Python中找到最长可能的棍子长度？

假设我们有一个整数棍棒列表。这里，列表中的每个元素代表一个带有两个末端的棒，这些值在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，并访问一个集合

• 如果edge_idx不为null，则

• 从已访问中删除edge_idx

• n_node：= sticks [e_idx，1]与sticks [e_idx，1]相同，否则，sticks [e_idx，1]

• res：= res的最大值和1 + dfs（n_node，e_idx，访问）

• 返回0

• 如果访问了edge_idx，则

• 将edge_idx标记为已访问

• res：= 0

• 对于g [node]中的每个e_idx，执行

• 如果edge_idx不为零，则

• 返回资源

• 从主要方法执行以下操作：

• 棒：=棒中所有s的列表（s [0]，s [1]）

• 顶点：=一个新集合

• g：=一个空的映射

• 对于每个索引i和棍子的边缘，执行

• 将我插入g [edge [0]]

• 将我插入g [edge [1]]

• 将edge [0]和edge [1]插入顶点

• res：= 0

• 对于顶点中的每个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