Pythonで可能な限り長いスティックの長さを見つけるプログラム？

整数スティックのリストがあるとします。ここで、リスト内の各要素は2つの端を持つスティックを表し、これらの値は1〜6です。これらは各端を表しています。両端が同じであれば、2本のスティックをつなぐことができます。結果として得られるスティックの端は残りの端になり、その長さが長くなります。可能な限り長いスティックの長さを見つける必要があります。

したがって、入力がsticks =[[2、3]、[2、4]、[3、5]、[6、6]]のようである場合、[2、3を接続できるため、出力は3になります。 ]と[2、4]で[3、4]を取得し、[3、5]と接続して[4、5]を取得できます。

これを解決するには、次の手順に従います。

• 関数dfs（）を定義します。これにより、ノード、edge_idx、および訪問されたセットが取得されます

• edge_idxがnullでない場合、

  • edge_idxにアクセスした場合、

    • 0を返す

  • edge_idxを訪問済みとしてマーク

  • res：=0

  • g [node]のe_idxごとに、実行

    • n_node：=sticks [e_idx、0]（sticks [e_idx、1]がノードと同じ場合）それ以外の場合はsticks [e_idx、1]

    • res：=resの最大値と1+ dfs（n_node、e_idx、visited）

  • edge_idxがゼロ以外の場合、

    • 訪問先からedge_idxを削除

  • 解像度を返す

• メインの方法から、次の手順を実行します。

• スティック：=スティック内のすべてのsのリスト（s [0]、s [1]）

• 頂点：=新しいセット

• g：=空の地図

• 各インデックスiとスティックのエッジについて、実行します

  • iをg[edge[0]]

    に挿入します

  • iをg[edge[1]]

    に挿入します

  • edge[0]とedge[1]を頂点に挿入します

• res：=0

• 頂点の各vについて、実行します

  • res：=resとdfsの最大値（v、null、および空集合）

• 戻り値-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