Tìm độ dài que gỗ dài nhất có thể tạo trong Python

Cho list sticks, mỗi que có 2 đầu giá trị 1..6. Nối 2 que nếu có đầu chung, que mới có 2 đầu còn lại, độ dài +1. Tìm độ dài tối đa.

Ví dụ: sticks = [[2,3],[2,4],[3,5],[6,6]] → 3 (nối [2,3]+[2,4]=[3,4], nối [3,5]=[4,5]).

Giải pháp: Mô hình đồ thị (đỉnh=giá trị đầu, cạnh=que). Tìm đường đi đơn giản dài nhất (simple path) bằng DFS backtracking trên đồ thị nhỏ (đỉnh 1..6).

Ví dụ triển khai

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, (u, v) in enumerate(sticks):
            g[u].add(i)
            g[v].add(i)
            vertices.add(u)
            vertices.add(v)
        
        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

Đầu vào

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

Đầu ra

3