BFS2

View as PDF
Submit solution
Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout
Author:
admin
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho một đơn đồ thị liên thông gồm N đỉnh và N−1 cạnh. Mỗi cạnh có độ dài bằng 1. Ta nói đây là một cây không trọng số. Đường kính của cây là khoảng cách giữa hai đỉnh xa nhau nhất. Tâm của cây là đỉnh mà có khoảng cách từ nó tới nút xa nó nhất là nhỏ nhất. Một cây có thể có nhiều tâm. Hãy tìm đường kính của cây và các tâm của cây.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương N
  • N−1 dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x và y chỉ một cạnh nối giữa hai đỉnh x và y trên cây.

Giới hạn:

  • 1 ≤ N ≤ ~10^5~

Kết quả:

  • Dòng đầu tiên, in ra đường kính của cây.
  • Dòng thứ hai, in ra số lượng tâm của cây.
  • Dòng thứ ba, in ra các đỉnh là tâm của cây theo thứ tự tăng dần. Các số cách nhau bởi 1 dấu cách.
Ví dụ:
Input 1:
5
1 2
2 3
3 4
2 5
Output 1:
4
2
2 3

Comments

Please read the guidelines before commenting.


  • 5
    Nhatthang27  commented on March 16, 2023, 5:39 a.m. ← edit 4

    Ta có vài khái niệm cần chú ý:

    • Khoảng cách giữa hai nút (trên cây không trọng số) là số cạnh nốt hai nút đó.
    • Đường kính của cây là khoảng cách giữa hai đỉnh xa nhau nhất trên cây.

    • Tâm của cây là nút nằm giữa trên đường kính. Một cây sẽ có tối đa 2 tâm. (Nếu đường kính độ dài chẳn (độ dài tính theo cạnh) thì tâm sẽ là nút ở giữa, ngược lại nếu là lẻ thì là 2 nút ở giũa. Nếu trường hợp có hai hay nhiều hơn các đường kính, thì các đường kính sẽ có cùng độ dài và cắt nhau ở tâm. Điều này không cần phải bận tâm khi cài đặt, ta chỉ cần tìm 1 đường kính duy nhất và tìm tâm của nó, tâm đó sẽ là tâm của tất cả các đường kính và cũng là tâm của cây).

      Ví dụ : enter image description here

      Đoạn từ nút 4 tới nút 5 sẽ là đường kính của cây, có độ dài là 3. (Tuy nhiên, trong bài này thì mình cần cho output là số đỉnh trên đường kính chứ không phải độ dài, dù là câu hỏi nào thì việc trả lời cũng tương đương nhau.) Tâm của cây sẽ là nút 2 và 3.

    • Đường đi giữa hai nút bất kì trên cây là duy nhất.

    • Một trong hai đầu mút của đường kính của cây luôn có khoảng cách xa nhất đến một nút bất kỳ trong cây. (Ta chứng minh bằng phản chứng: giả sử đầu mút đó không có khoảng cách xa nhất đến bất kỳ nút nào trong cây, thì chúng ta có thể chọn một nút xa nhất từ đầu mút này và chọn nút xa nhất từ nút đó để tạo thành đường kính mới dài hơn. Điều này mâu thuẫn với giả định rằng đường kính của cây đã được chọn và có độ dài lớn nhất. Do đó, một trong hai đầu mút của đường kính của cây phải có khoảng cách xa nhất đến một nút bất kỳ trong cây).

    Thuật toán:

    1. Từ một nút bất kì (có thể là nút gốc) gọi là A, duyệt DFS tìm nút có khoảng cách xa nhất với A, gọi là B. Theo định lí trên, nút B chắc chắn là một trong hai đầu mút của đường kính.
    2. Từ nút B, duyệt DFS tìm nút có gọi cách xa nhất với B, gọi là C. Lúc này BC sẽ là đường kính của cây.
    3. Sau đó duyệt lại các nút đã lưu trên đường kính, rồi tìm tâm.

    Cài đặt:

    1. Viết hàm DFS với cái parameter là root, parent và depth[ DFS(root, parent, depth)]. Gọi DFS(root, -1, 0) tìm nút cách xa nút root (root có thể là 1) nhất. Gọi đó là nút u.
    2. Duyệt DFS(u, -1, 0) tìm nút cách xa nút u nhất. Gọi là nút v.
    3. Khoảng cách u -> v sẽ là đường kính. Vì đường đi trên cây là duy nhất nên ta duyệt ngược lại để truy vết các nút nằm trên đường kính. (Ta có thể duyệt theo kiểu v lên parent của v, và cứ thế cho đến khi gặp u)
    4. Sau khi có các nút trên đường kính thì việc tìm tâm là dễ dàng.

    GoodLuck