Liên thông trên cây phiên bản
Đề bài
Mô tả
Cho đỉnh được đánh số từ đến . Phiên bản của đồ thị không có cạnh nào.
Có thao tác được thực hiện lần lượt, mỗi thao tác thuộc một trong hai dạng:
1 p u v— tạo một phiên bản mới bằng cách lấy phiên bản rồi thêm vào đó cạnh vô hướng . Nếu đây là thao tác dạng thứ thì phiên bản mới được đánh số là . Phiên bản không bị thay đổi. Cho phép (khuyên) và cho phép thêm một cạnh đã có (cạnh bội).2 p u v— truy vấn trên phiên bản : nếu và thuộc cùng một thành phần liên thông thì in ra số đỉnh của thành phần đó, ngược lại in ra .
Như vậy các phiên bản không xếp thành một dãy: một phiên bản có thể được dùng làm gốc cho nhiều phiên bản mới khác nhau. Dữ liệu đảm bảo luôn là số hiệu của một phiên bản đã tồn tại ngay trước khi thực hiện thao tác đó.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và .
- dòng tiếp theo, mỗi dòng chứa bốn số nguyên mô tả một thao tác theo đúng định dạng ở trên.
Dữ liệu ra
Với mỗi thao tác dạng , in ra một dòng chứa đáp số tương ứng, theo thứ tự xuất hiện.
Ràng buộc
- số phiên bản đã được tạo trước thao tác đang xét
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 7 1 0 1 2 1 1 2 3 2 2 1 3 1 1 4 5 2 3 1 3 2 3 4 5 2 0 1 1 |
3 -1 2 1 |
Phiên bản 1 có cạnh (1,2); phiên bản 2 là phiên bản 1 thêm cạnh (2,3) nên 1 và 3 cùng một thành phần gồm 3 đỉnh. Phiên bản 3 lại xuất phát từ phiên bản 1 (không phải phiên bản 2) và thêm cạnh (4,5), nên ở đó đỉnh 1 và 3 không nối nhau, còn 4 và 5 tạo thành phần 2 đỉnh. Truy vấn cuối hỏi trên phiên bản 0: đỉnh 1 luôn cùng thành phần với chính nó, thành phần đó chỉ có 1 đỉnh. |
| 3 6 1 0 1 1 2 1 1 2 1 1 1 2 1 2 1 2 2 3 1 2 2 2 2 3 |
-1 2 -1 |
Phiên bản 1 chỉ có khuyên (1,1) nên không nối 1 với 2. Phiên bản 3 thêm cạnh (1,2) lần thứ hai, cạnh bội này không làm thành phần lớn thêm: đáp số vẫn là 2. Trên phiên bản 2, đỉnh 3 vẫn đứng riêng. |
Bình luận