Tóm tắt đề bài

Cho đồ thị vô hướng gồm \(N\) đỉnh ban đầu không có cạnh nào. Xử lý \(Q\) truy vấn thuộc một trong ba loại:

1. 1 x y: Thêm một cạnh nối giữa \(x\) và \(y\).
2. 2 x y: Xóa một cạnh nối giữa \(x\) và \(y\) (nếu có nhiều cạnh giữa \(x\) và \(y\), xóa một cạnh bất kỳ; nếu không có, bỏ qua).
3. 3 x y: Kiểm tra xem hai đỉnh \(x\) và \(y\) có liên thông với nhau hay không.

Kết quả của tất cả các truy vấn loại \(3\) được ghép lại và in ra trên cùng một dòng.

Phân tích

• Ràng buộc: \(N, Q \le 10^5\). Trong \(50\%\) số test, \(N, Q \le 5000\).
• Đồ thị là đa đồ thị (multigraph), tức là có thể tồn tại nhiều cạnh song song giữa hai đỉnh.
• Việc vừa thêm cạnh, vừa xóa cạnh và kiểm tra liên thông là bài toán kinh điển: Dynamic Connectivity Offline.
• Vì toàn bộ \(Q\) truy vấn đều được biết trước, ta có thể xác định khoảng thời gian tồn tại \([L, R]\) của từng cạnh, sau đó sử dụng Segment Tree theo trục thời gian kết hợp với DSU có khả năng hoàn tác (DSU with Rollback).

Cách làm đơn giản (Brute Force)

Ý tưởng

• Duy trì đồ thị hiện tại bằng danh sách kề (hoặc ma trận kề / bảng đếm số cạnh giữa hai đỉnh).
• Với truy vấn loại \(1\): Thêm cạnh \((x, y)\).
• Với truy vấn loại \(2\): Xóa bớt một cạnh \((x, y)\) nếu tồn tại.
• Với truy vấn loại \(3\): Chạy thuật toán tìm kiếm theo chiều rộng (BFS) hoặc tìm kiếm theo chiều sâu (DFS) từ đỉnh \(x\) để kiểm tra xem có đi tới được đỉnh \(y\) hay không.

Độ phức tạp

• Thời gian:
  • Truy vấn loại \(1, 2\): \(O(1)\).
  • Truy vấn loại \(3\): Mỗi lần chạy BFS/DFS mất \(O(N + E)\) với \(E\) là số cạnh hiện có (\(E \le Q\)).
  • Tổng thời gian: \(O(Q \times (N + Q))\), quá chậm với \(N, Q = 10^5\), nhưng phù hợp cho \(N, Q \le 5000\) (khoảng \(50\%\) số test).
• Bộ nhớ: \(O(N + Q)\).

Hướng giải quyết (Tối ưu)

Nhận xét

1. Mỗi cạnh \((u, v)\) được tạo ra ở thời điểm \(t_{start}\) và tồn tại đến thời điểm \(t_{end}\) (trước khi bị xóa bởi truy vấn loại 2, hoặc kéo dài đến hết truy vấn \(Q\) nếu không bị xóa).
2. Khi một cạnh tồn tại trên đoạn thời gian \([t_{start}, t_{end}]\), ta có thể chèn cạnh này vào cây phân đoạn (Segment Tree) quản lý các đoạn thời gian từ \(1\) đến \(Q\). Một đoạn thời gian \([t_{start}, t_{end}]\) sẽ được phân rã thành \(O(\log Q)\) nút trên Segment Tree.
3. Sau khi dựng cây xong, ta duyệt DFS trên Segment Tree:
   • Khi đi vào một nút, thêm tất cả các cạnh lưu tại nút đó vào DSU.
   • Khi đến lá \(t\), nếu tại thời điểm \(t\) có truy vấn loại \(3\), ta dùng hàm find của DSU để kiểm tra \(u\) và \(v\) có cùng gốc hay không.
   • Khi duyệt xong một nút và chuẩn bị quay lui (backtrack), ta hoàn tác (rollback) lại các thao tác DSU đã thực hiện ở nút đó.

DSU with Rollback (DSU có hoàn tác)

• Không dùng nén đường đi (Path Compression) vì nó phá vỡ cấu trúc cây và khó hoàn tác.
• Dùng kỹ thuật gộp theo kích thước (Union by Size / Rank) để chiều cao cây luôn là \(O(\log N)\).
• Lưu lịch sử các thay đổi vào một ngăn xếp (history), mỗi khi gộp hai gốc ta ghi nhận lại gốc nào được gán vào gốc nào để khi rollback chỉ cần khôi phục lại kích thước và quan hệ cha-con.

Xử lý Đa đồ thị

• Vì có thể có nhiều cạnh giữa \((u, v)\), ta chuẩn hóa \(u < v\) và lưu các thời điểm bắt đầu xuất hiện vào một danh sách hoặc ngăn xếp (vector / multiset) tương ứng với cặp \((u, v)\).
• Khi gặp truy vấn xóa cạnh \((u, v)\), ta lấy một mốc thời điểm bắt đầu chưa kết thúc ra, ghép thành đoạn \([t_{start}, t_{delete} - 1]\) và thêm vào Segment Tree.

Độ phức tạp

• Thời gian:
  • Mỗi cạnh được chèn vào \(O(\log Q)\) nút trên Segment Tree.
  • Mỗi thao tác gộp DSU mất \(O(\log N)\).
  • Tổng thời gian: \(O(Q \log Q \log N)\), hoàn toàn chạy tốt với \(N, Q = 10^5\) trong giới hạn 1-2 giây.
• Bộ nhớ: \(O(N + Q \log Q)\) để lưu Segment Tree và cấu trúc DSU.