Nước lạnh

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập \(N\) nhánh (đánh số từ \(1...N\)) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác \(2\) nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là \(1\).

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

"Phần cuối" của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có \(C\) nút ống, được mô tả bằng \(3\) số nguyên: là "phần cuối" của ống \(E_{i}\) và \(2\) ống nhánh đi ra từ đó là \(B_{1i}\) và \(B_{2i}\). Đường ống số \(1\) nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là \(1\).

Input

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: \(N\) và \(C\)
  • Dòng \(2...C+1\): Dòng \(i+1\) mô tả nút ống \(i\) với ba số nguyên cách nhau bởi dấu cách: \(E_{i},B_{1i}\), và \(B_{2i}\).

Output

  • Dòng \(1...N\): Dòng \(i\) chứa \(1\) số nguyên là khoảng cách từ chuồng tới "phần cuối" của ống thứ \(i\).

Constraints

  • \(3 \leq N \leq 99999\), \(N\) lẻ
  • \(1 \leq C \leq N\)
  • \(1 \leq E_{i} \leq N\)
  • \(2 \leq B_{1i}, B_{2i} \leq N\)

Example

Test 1

Input
5 2
3 5 4
1 2 3 
Output
1
2
2
3
3
Note

Dữ liệu ở trên mô tả bản đồ ống nước sau:
+-––––––-+
| Chuồng |
+-––––––-+
| 1
*
2 / \ 3
*
4 / \ 5
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên khoảng cách sẽ là 3.
```


Bình luận


  • 5
    jumptozero 9:41 a.m. 1 Tháng 6, 2021

    Mình xin chia sẻ lời giải bài này như sau:

    Đầu tiên, ta sẽ thực hiện một phép biến đổi đồ thị đã cho thành đồ thị tương tự nhưng vẫn đảm bảo không thay đổi kết quả của bài toán

    Cụ thể như sau:

    Ứng với mỗi cạnh trong đồ thị ban đầu, sẽ là \(1\) đỉnh của đồ thị sau khi biến đối. (Các bạn có thể xem hình bên dưới)

    Như vậy bài toán đã cho quy về bài toán: tìm khoảng cách từ đỉnh \(1\) đến tất cả các đỉnh => Đây chính bài toán tương tự bài bfs cơ bản.

    Gọi mảng \(d[]\) là mảng trong đó \(d[i]\) chính là khoảng cách từ đỉnh \(i\) đến đỉnh \(1\). Khi đó ta chỉ cần in ra \(d[i]+1\) với mỗi \(i\) chạy từ \(1\) đến \(n\)

    Như vậy là bài toán đã được giải quyết xong !

    Ps:

    • Nếu có gì thắc mắc, các bạn có thể comment.

    • Các bạn có thể tham khảo code của mình tại đây Link