Nước lạnh

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

Dạng bài

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

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập \(N\) nhánh (đánh số từ \(1...N\)) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác \(2\) nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là \(1\).

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

"Phần cuối" của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có \(C\) nút ống, được mô tả bằng \(3\) số nguyên: là "phần cuối" của ống \(E_{i}\) và \(2\) ống nhánh đi ra từ đó là \(B_{1i}\) và \(B_{2i}\). Đường ống số \(1\) nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là \(1\).

Input

Dòng 1: 2 số nguyên cách nhau bởi dấu cách: \(N\) và \(C\)
Dòng \(2...C+1\): Dòng \(i+1\) mô tả nút ống \(i\) với ba số nguyên cách nhau bởi dấu cách: \(E_{i},B_{1i}\), và \(B_{2i}\).

Output

Dòng \(1...N\): Dòng \(i\) chứa \(1\) số nguyên là khoảng cách từ chuồng tới "phần cuối" của ống thứ \(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

Note

Dữ liệu ở trên mô tả bản đồ ống nước sau:
+-––––––-+
| Chuồng |
+-––––––-+
| 1
*
2 / \ 3
*
4 / \ 5
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên khoảng cách sẽ là 3.
```

Bình luận

6
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

1 bình luận nữa