- Ta sẽ xử lý offline bài này.
- Ta cần phải xóa lần lượt các cạch theo truy vấn, vậy điều gì sẽ xảy ra nếu ta làm ngược lại? (Thêm các cạnh đó nhưng theo thứ tự ngược lại)
- Trả lời: Thay vì phải xóa từng cạnh theo tự thứ tự truy vấn, ta sẽ làm ngược lại, đó là thêm các cạnh được xóa theo thứ tự ngược lại bằng cấu trúc DSU, như vậy các cạnh chưa được thêm vào sẽ coi như là đã được xóa và lúc này chỉ cần trả lời truy vấn như bình thường.
- Các bước giải bài toán:
+ Nhận thấy sau khi thực hiện toàn bộ truy vấn thì đồ thị sẽ chỉ còn lại các cạnh chưa được nhắc đến trong truy vấn, do đó đầu tiên ta sẽ đọc toàn bộ truy vấn, đánh dấu lại cách cạnh bị xóa và thêm vào cấu trúc DSU các cạnh không bị xóa.
+ Lần lượt duyệt truy vấn theo thứ tự ngược lại, ta trả lời truy vấn trước, sau đó thêm vào cạnh e của truy vấn đó (union 2 đỉnh mà cạnh e nối qua).
+ In ra các câu trả lời theo thứ tự ngược lại.
- Gợi ý: Trong cấu trúc DSU, có thể dụng thêm mảng cnt[i] để đếm số lượng đỉnh trong thành phần liên thông với i, và i ở đây là nút đại diện tplt đó (để tìm số đỉnh của tplt chứa đỉnh u thì gọi cnt[findroot(u)]). Trong hàm union, sau khi hợp 2 tplt thì cần phải gán lại cnt[xroot] = cnt[xroot] + cnt[yroot] nếu đặt đại diện của yroot là xroot và ngược lại, ban đầu khởi tạo tất cả cnt[i] = 1.
lehoang
Created at
24 likes