Bài toán quản lý phiên bản
Đề bài
Mô tả
Trong kỹ thuật phần mềm, "hệ thống quản lý phiên bản" (VCS) có nhiệm vụ quản lý các thay đổi đối với một chương trình máy tính, một tài liệu hay các thông tin khác. Trong bài này, bạn cần cài đặt một VCS cho một đồ thị vô hướng.
Ban đầu, đồ thị có đỉnh và cạnh. VCS cần lưu giữ nhiều ảnh chụp (snapshot) của đồ thị. Các ảnh chụp được đánh chỉ số theo thứ tự thời gian bằng các số nguyên bắt đầu từ . Ảnh chụp ban đầu của đồ thị được tạo ngay từ đầu, có chỉ số . Sau đó bạn cần thực hiện thao tác trên đồ thị. Mỗi thao tác thuộc một trong các loại sau:
- ADD : thêm một cạnh mới nối hai đỉnh và ;
- CHECK : trên đồ thị hiện tại, kiểm tra hai đỉnh và có thuộc cùng một thành phần liên thông hay không;
- COMMIT: tạo một ảnh chụp mới của đồ thị hiện tại;
- QUERY : trên ảnh chụp thứ , kiểm tra hai đỉnh và có thuộc cùng một thành phần liên thông hay không.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (). Mỗi dòng trong dòng tiếp theo mô tả một thao tác theo một trong các dạng sau:
- A (): thao tác ADD;
- ? (): thao tác CHECK;
- C: thao tác COMMIT;
- Q (, , trong đó là số ảnh chụp đã được tạo tính đến thời điểm đó): thao tác QUERY.
Dữ liệu ra
Với mỗi thao tác CHECK hoặc QUERY, theo đúng thứ tự, in ra ký tự Y nếu hai đỉnh và thuộc cùng một thành phần liên thông, và ký tự N trong trường hợp ngược lại. Các ký tự được in liền nhau trên một dòng.
Ràng buộc
- .
- ; có thể bằng .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 9 A 1 2 ? 1 2 Q 0 1 2 C Q 1 1 2 A 1 3 C Q 1 1 3 Q 2 1 3 |
YNYNY | Ảnh chụp chưa có cạnh nào. Sau khi thêm cạnh : đồ thị hiện tại có và liên thông (Y) nhưng ảnh chụp thì không (N). Ảnh chụp có cạnh (Y). Sau khi thêm cạnh và tạo ảnh chụp : ảnh chụp không có cạnh (N), còn ảnh chụp thì có (Y). |
| 3 6 ? 2 2 A 2 3 C A 1 2 Q 1 1 3 ? 1 3 |
YNY | Một đỉnh luôn liên thông với chính nó. Ảnh chụp chỉ có cạnh nên và chưa liên thông, còn trên đồ thị hiện tại thì đã liên thông. |
Bình luận