DSU có hoàn tác

Buổi 25 — Disjoint Set Union Data-structures
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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ại 1 gần nhất chưa bị hoàn tác (đảm bảo luôn có thao tác loại 1 để 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 3 và 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$
Draft saved