DSU có hoàn tác
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho đồ thị $N$ đỉnh ban đầu không có cạnh nào. Thực hiện $Q$ thao tác thuộc các loại sau:
1 u v: Lưu trạng thái hiện tại vào lịch sử, sau đó thêm cạnh nối $u$ và $v$ (nếu $u, v$ đã liên thông thì không có thay đổi nhưng vẫn tính là một thao tác lưu trạng thái).2: Hoàn tác thao tác loại1gần nhất chưa bị hoàn tác (đảm bảo luôn có thao tác loại1để hoàn tác).3 u v: Kiểm tra $u$ và $v$ có liên thông hay không (YES/NO).4: In ra số thành phần liên thông hiện tại.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $Q$ dòng tiếp theo mô tả các truy vấn.
Dữ liệu ra
- In ra kết quả cho mỗi truy vấn loại
3và4.
Ví dụ
| Input | Output |
|---|---|
| 4 7 1 1 2 1 2 3 3 1 3 4 2 3 1 3 4 |
YES 2 NO 3 |
Giới hạn
- $1 \le N, Q \le 10^5$
Community Discussion