โปรแกรมเชื่อมต่อฟอเรสต์ใน Python

สมมติว่าเรามีกราฟเป็นรายการที่อยู่ติดกัน กราฟนี้เป็นชุดของต้นไม้ที่ไม่ปะติดปะต่อกัน เราต้องเพิ่มจำนวนขอบป่าให้กลายเป็นต้นไม้ต้นเดียว เราต้องคืนค่าระยะทางต่ำสุดที่เป็นไปได้ของเส้นทางที่ยาวที่สุดระหว่างสองโหนด ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 4

เราสามารถเพิ่มขอบได้ 0 −> 5 จากนั้น เส้นทางที่ยาวที่สุดอาจเป็น 3 −> 1 −> 0 −> 5 −> 7 หรือ 4 −> 1 −> 0 −> 5 −> 7; และเส้นทางเหล่านี้ด้วยทิศทางกลับด้าน ดังนั้นเราจึงกลับระยะทาง 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เห็นแล้ว :=ชุดใหม่

• dic :=กราฟ

• กำหนดฟังก์ชัน treeDepth() นี่จะใช้โหนด

  • ยกเลิก :=0

  • กำหนดฟังก์ชัน dfs1() นี่จะใช้โหนดพาเรนต์

    • เพิ่มโหนดในชุดที่เห็น

    • best2 :=โครงสร้างฮีปขั้นต่ำที่ว่างเปล่า

    • สำหรับแต่ละ nxt ใน dic[node] ทำ

      • ถ้า nxt ไม่เหมือนกับ parent แล้ว

        • push(dfs1(nxt, node) + 1) เป็น best2

      • ถ้า len(best2)> 2 แล้ว

        • ป๊อปจากกอง (ดีที่สุด2)

      • ถ้า best2 ว่างเปล่า แล้ว

        • คืนค่า 0

      • ret :=สูงสุดของ ret, ผลรวมขององค์ประกอบทั้งหมดที่ดีที่สุด2

      • ผลตอบแทนสูงสุดที่ดีที่สุด2

    • dfs1(โหนด, null)

    • รีเทิร์น

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• ret :=0, opt :=รายการใหม่, ร้องเพลง :=0

  • สำหรับโหนดในช่วง 0 ถึงขนาดของกราฟ ให้ทำ

    • หากมองเห็นโหนดแล้ว

      • ไปทำซ้ำต่อไป

    • res :=treeDepth(โหนด)

    • sing :=สูงสุดของ sing, res

    • ใส่เพดานของ (res / 2) ที่ส่วนท้ายของ opt

  • ถ้าขนาดของ opt <=1 แล้ว

    • กลับมาร้องเพลง

  • mx :=ตัวเลือกสูงสุด

  • สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ opt ทำ

    • ถ้า opt[i] เหมือนกับ mx แล้ว

      • opt[i] :=opt[i] − 1

      • ออกจากวง

  • สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ opt ทำ

    • opt[i] :=opt[i] + 1

  • high2 :=องค์ประกอบ 2 ที่ใหญ่ที่สุดจาก opt.

  • ผลตอบแทนสูงสุด (high2) และร้องเพลง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

import heapq, math
class Solution:
   def solve(self, graph):
      seen = set()
      dic = graph
      def treeDepth(node):
         self.ret = 0
         def dfs1(node, parent):
            seen.add(node)
            best2 = []
            for nxt in dic[node]:
               if nxt != parent:
                  heapq.heappush(best2, dfs1(nxt, node) + 1)
                  if len(best2) > 2:
                     heapq.heappop(best2)
            if not best2:
               return 0
            self.ret = max(self.ret, sum(best2))
            return max(best2)
         dfs1(node, None)
         return self.ret
      ret = 0
      opt = []
      sing = 0
      for node in range(len(graph)):
         if node in seen:
            continue
         res = treeDepth(node)
         sing = max(sing, res)
         opt.append(int(math.ceil(res / 2)))
      if len(opt) <= 1:
         return sing
      mx = max(opt)
      for i in range(len(opt)):
         if opt[i] == mx:
            opt[i] −= 1
            break
         for i in range(len(opt)):
            opt[i] += 1
         high2 = heapq.nlargest(2, opt)
         return max(sum(high2), sing)
ob = Solution()
graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]
print(ob.solve(graph))

อินพุต

graph = [
   [1, 2],
   [0,3,4],
   [0],
   [1],
   [1],
   [6,7],
   [5],
   [5]
]

ผลลัพธ์

4