หาความยาวไม้กาวที่ยาวที่สุดจากการต่อไม้กาวใน Python

มีลิสต์ไม้กาว sticks แต่ละอันมีปลาย 2 ด้าน (ค่า 1-6) ต่อได้ก็ต่อเมื่อปลายตรงกัน ไม้ใหม่มีปลายเป็นปลายที่เหลือ ความยาวเพิ่มขึ้น หาความยาวสูงสุด

ตัวอย่าง: sticks = [[2,3], [2,4], [3,5], [6,6]] → 3 (ต่อ [2,3]+[2,4]=[3,4] → +[3,5]=[4,5])

แนวทาง (DFS บนกราฟ)

1. สร้างกราฟ: โหนด = ค่าปลาย (1-6), ขอบ = ไม้กาว (เก็บ index)
2. DFS จากทุกโหนด หาเส้นทางยาวที่สุดที่ไม่ใช้ขอบซ้ำ
3. ใช้ visited set ติดตามขอบที่ใช้แล้ว
4. คืนความยาวสูงสุด - 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))  # 3

อินพุต

sticks = [[2, 3], [2, 4], [3, 5], [6, 6]]

เอาต์พุต

3