โปรแกรมเชื่อม Forest ให้กลายเป็น Tree เดียว ระยะทางสูงสุดน้อยที่สุดใน Python

ได้รับ Forest (ชุดต้นไม้แยกกัน) ต้อง เพิ่มขอบเพื่อเชื่อมเป็น Tree เดียว โดยทำให้ เส้นทางยาวที่สุด (diameter) น้อยที่สุด คืนค่า diameter นั้น

ตัวอย่าง

Graph: สองต้นไม้แยกกัน

Tree 1:     0         Tree 2:     5
           / \                 / \
          1   2               6   7
         / \
        3   4

Output: 4

เชื่อม 0-5 → diameter = 4 (path 3-1-0-5-7)

แนวทางแก้ปัญหา

1. หา Diameter และ Radius (ceil(diameter/2)) ของแต่ละต้นไม้ใน Forest
2. Radius = ระยะห่างจากศูนย์กลางไปยังใบไกลสุด
3. เชื่อมต้นไม้โดยต่อ Radius ใหญ่ที่สุดกับตัวที่สองใหญ่สุด
4. คำตอบ = max( max_diameter, largest_radius + second_largest_radius + 1 )
5. รายละเอียด: ลด radius ใหญ่สุดลง 1 (เพราะเชื่อมที่ศูนย์กลาง) แล้วบวก 1 ทุก radius (ขอบเชื่อม)

การใช้งาน (Python)

import heapq
import math

class Solution:
    def solve(self, graph):
        n = len(graph)
        seen = set()
        
        def tree_diameter(node):
            # Return (diameter, radius) of tree containing node
            self.dia = 0
            
            def dfs(u, parent):
                seen.add(u)
                best = [0, 0]  # two longest depths
                for v in graph[u]:
                    if v != parent:
                        d = dfs(v, u) + 1
                        if d > best[0]:
                            best = [d, best[0]]
                        elif d > best[1]:
                            best[1] = d
                self.dia = max(self.dia, best[0] + best[1])
                return best[0]
            
            dfs(node, -1)
            radius = (self.dia + 1) // 2
            return self.dia, radius
        
        diameters = []
        radii = []
        max_dia = 0
        
        for i in range(n):
            if i not in seen:
                dia, rad = tree_diameter(i)
                diameters.append(dia)
                radii.append(rad)
                max_dia = max(max_dia, dia)
        
        if len(radii) <= 1:
            return max_dia
        
        # Connect trees optimally
        radii.sort(reverse=True)
        # Reduce largest by 1 (connect at center), add 1 to all (new edges)
        radii[0] -= 1
        radii = [r + 1 for r in radii]
        radii.sort(reverse=True)
        
        return max(max_dia, radii[0] + radii[1])

# ทดสอบ
ob = Solution()
graph = [
    [1, 2], [0, 3, 4], [0], [1], [1],
    [6, 7], [5], [5]
]
print(ob.solve(graph))  # Output: 4

ความซับซ้อน

• Time Complexity: O(V + E)
• Space Complexity: O(V)