Python - Độ dài đường đi dài nhất trong cây n-ary

Cho danh sách cạnh (u, v) biểu diễn cây (u là cha của v). Tìm độ dài đường đi dài nhất trong cây. Độ dài đường đi = 1 + số nút trên đường đi.

Ví dụ

Cạnh: [(1,2),(1,3),(1,4),(4,5),(5,7),(1,6),(4,8)]
Output: 5
Đường đi: [1, 4, 5, 7] (4 nút) → độ dài = 1 + 4 = 5.

Thuật toán: BFS 2 lần (Tìm đường kính cây)

Đường đi dài nhất trong cây = đường kính (diameter) của cây. Tìm bằng 2 lần BFS:

1. BFS từ nút bất kỳ → tìm nút xa nhất f
2. BFS từ f → tìm nút xa nhất f2, khoảng cách d[f2] là đường kính

Mã Python

def solve(edges):
    # Xây dựng danh sách kề (undirected)
    g = {}
    for u, v in edges:
        g.setdefault(u, []).append(v)
        g.setdefault(v, []).append(u)
    
    def bfs(start):
        """Trả về nút xa nhất từ start"""
        dist = {start: 1}
        farthest = start
        queue = [start]
        
        for u in queue:
            for v in g[u]:
                if v not in dist:
                    dist[v] = dist[u] + 1
                    if dist[v] > dist[farthest]:
                        farthest = v
                    queue.append(v)
        return farthest
    
    # BFS lần 1: tìm nút xa nhất từ nút bất kỳ
    arbitrary = next(iter(g))
    far = bfs(arbitrary)
    
    # BFS lần 2: từ nút xa nhất tìm đường kính
    return bfs(far)  # Trả về khoảng cách (đã +1 theo định nghĩa đề bài)

# Test
edges = [(1,2),(1,3),(1,4),(4,5),(5,7),(1,6),(4,8)]
print(solve(edges))  # Output: 5

Phân tích độ phức tạp

• Thời gian: O(N) - 2 lần BFS, mỗi cạnh duyệt 2 lần
• Không gian: O(N) - lưu đồ thị và khoảng cách

Lưu ý

• Đề bài định nghĩa độ dài = 1 + số nút. BFS trả về khoảng cách tính bằng số nút (khởi tạo dist[start]=1).
• Cây n-ary được xử lý như cây không hướng (undirected) để BFS hoạt động đúng.