โปรแกรมหาความยาวของแท่งไม้ที่ยาวที่สุดใน Python?

สมมติว่าเรามีรายชื่อแท่งจำนวนเต็ม แต่ละองค์ประกอบในรายการแสดงถึงแท่งไม้ที่มีปลายทั้งสองด้าน ค่าเหล่านี้อยู่ระหว่าง 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 ว่าเข้าชมแล้ว

  • res :=0

  • สำหรับแต่ละ e_idx ใน g[node] ให้ทำ

    • n_node :=sticks[e_idx, 0] เมื่อ sticks[e_idx, 1] เหมือนกับ node มิฉะนั้น sticks[e_idx, 1]

    • res :=สูงสุดของ res และ 1 + dfs(n_node, e_idx, เข้าชมแล้ว)

  • ถ้า edge_idx ไม่ใช่ศูนย์ แล้ว

    • ลบ edge_idx จากการเยี่ยมชม

  • ผลตอบแทน

• จากวิธีหลัก ให้ทำดังนี้:

• sticks :=รายการสำหรับ s ทั้งหมดใน sticks (s[0], s[1])

• จุดยอด :=ชุดใหม่

• g :=แผนที่ว่างเปล่า

• สำหรับแต่ละดัชนี i และขอบเป็นแท่ง ให้ทำ

  • แทรก i ลงใน g[edge[0]]

  • แทรก i ลงใน g[edge[1]]

  • แทรกขอบ[0] และขอบ[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