Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Đường kính của cây

Một cây là một đồ thị vô hướng liên thông không có chu trình.

Bạn sẽ học được gì

  • Tìm đỉnh xa nhất bằng một lần duyệt
  • Dùng hai lần BFS để tìm đường kính
  • Biểu diễn cây bằng danh sách kề

Đề bài

Xem bản gốc (English)

Một cây là một đồ thị vô hướng liên thông không có chu trình. Đường kính của cây là số cạnh lớn nhất trên một đường đi giữa hai đỉnh bất kỳ. Hãy trả về độ dài đó; bạn không cần trả về đường đi. Không có đỉnh gốc được chỉ định.

Cài đặt hàm tree_diameter(vertices, edges).

Đầu vào

vertices: Số lượng đỉnh.

edges: Các cạnh vô hướng dạng [u, v].

Đầu ra

Trả về đường kính tính theo số cạnh, không phải số đỉnh.

Ràng buộc

1 ≤ vertices ≤ 200.000. Có đúng vertices − 1 cạnh, với các đầu mút khác nhau trong khoảng 1…vertices. Đầu vào luôn tạo thành một cây. Cây chỉ có một đỉnh thì đường kính là 0.

Ví dụ

Ví dụ 1
Đầu vào:
vertices = 5
edges = [
    [1, 2],
    [2, 3],
    [3, 4],
    [2, 5]
]

Kết quả mong đợi:
expected = 3
Đầu vào:
long long vertices = 5;
std::vector<std::vector<long long>> edges = {
    {1, 2},
    {2, 3},
    {3, 4},
    {2, 5}
};

Kết quả mong đợi:
long long expected = 3;
Đầu vào:
long vertices = 5;
long[][] edges = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 4},
    new long[] {2, 5}
};

Kết quả mong đợi:
long expected = 3;

Giải thích

Đường đi 5–2–3–4 gồm ba cạnh. Không có đường đi nào trong cây này dài hơn.

Ví dụ 2
Đầu vào:
vertices = 1
edges = []

Kết quả mong đợi:
expected = 0
Đầu vào:
long long vertices = 1;
std::vector<std::vector<long long>> edges = {};

Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long vertices = 1;
long[][] edges = new long[][] {};

Kết quả mong đợi:
long expected = 0;

Giải thích

Một đỉnh đơn lẻ không có cạnh nào, nên độ dài đường đi dài nhất là 0.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Trong cây, đường đi dài nhất có thể tìm bằng hai lần tìm kiếm đồ thị thay vì kiểm tra mọi cặp đỉnh.

Gợi ý 2

Bắt đầu từ một đỉnh bất kỳ, tìm đỉnh xa nhất, rồi tìm lại từ đó để đo khoảng cách lớn nhất.

Gợi ý 3

Đếm cạnh, không đếm đỉnh, và nhớ rằng cây chỉ có một đỉnh thì diameter bằng zero.

Độ phức tạp mong đợi

thời gian O(vertices), bộ nhớ phụ O(vertices)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 825 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.