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

假设我们有一个整数 sticks 的列表，其中列表中的每个元素代表两个端点的棍子，这些值在1和6之间。我们可以将两个棍子连接起来，如果它们的任何一端相同。结果棍子的末端将是剩余的末端，其长度增加了。我们必须找到可能的最长棍子的长度。

因此，如果输入为 sticks = [[2,3]，[2,4]，[3,5]，[6,6]]，则输出将是3，因为我们可以连接[2,3]和[2,4]以获取[3, 4]，然后我们可以将其与[3, 5]连接以获取[4, 5]。

为了解决这个问题，我们将按照以下步骤进行：

• 定义一个函数 dfs()。这将接收节点、edge_idx 和一个 set visited。

• 如果 edge_idx 不为空，则

  • 如果 edge_idx 已被访问，则
    • 返回0
  • 标记 edge_idx 为visited

  • res := 0

  • 对于 g\[node] 中的每个 e_idx，执行以下操作：

    • n_node := sticks[e_idx, 0] when sticks[e_idx, 1] is same as node otherwise sticks[e_idx, 1]

    • res := maximum of res and 1 + dfs(n_node, e_idx, visited)

  • 如果 edge_idx 为非零，则

    • 从visited中删除edge_idx
  • 返回res

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

• sticks := 用于所有 s in sticks 的列表（s[0]，s[1]）

• vertices := 一个新set

• g := 一个空映射

• 对于sticks中的每个索引 i 和边缘，执行以下操作：

  • 将 i 插入到g[edge[0]]中

  • 将 i 插入到 g[edge[1]] 中

  • 将edge[0]和edge[1]插入到vertices中

• res := 0

• 对于 vertices 中的每个 v，执行以下操作：

  • res := maximum of res and 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] == nodeelse 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