Tóm tắt đề bài

Cho một đồ thị vô hướng, liên thông gồm \(N\) đỉnh và \(M\) cạnh có trọng số. Cho \(Q\) truy vấn, mỗi truy vấn gồm một tập chỉ số cạnh \(S_i\). Cần xác định xem liệu có tồn tại ít nhất một cây khung nhỏ nhất (MST) của đồ thị chứa toàn bộ các cạnh trong \(S_i\) hay không.

Phân tích

• Điều kiện: \(2 \leq N, M \leq 5 \cdot 10^5\), \(Q \leq 5 \cdot 10^5\), tổng số cạnh qua các truy vấn \(\sum k_i \leq 5 \cdot 10^5\). Trọng số các cạnh \(1 \leq w_i \leq 10^5\).
• Tính chất của thuật toán Kruskal:
  • Khi thuật toán Kruskal xét các cạnh theo thứ tự trọng số tăng dần, trạng thái liên thông (các thành phần liên thông) sau khi xử lý xong toàn bộ các cạnh có trọng số \(< W\) là duy nhất, không phụ thuộc vào việc ta chọn cạnh nào trong số các cạnh có cùng trọng số nhỏ hơn \(W\).
  • Do đó, các cạnh trong tập truy vấn \(S_i\) có trọng số \(W\) chỉ cạnh tranh với nhau và kết nối các thành phần liên thông đã được tạo bởi các cạnh có trọng số \(< W\).
  • Một tập cạnh \(S_i\) có thể thuộc một MST nào đó khi và chỉ khi: với mọi mức trọng số \(W\), các cạnh trong \(S_i\) có trọng số \(W\) không tạo thành bất kỳ chu trình nào khi được thêm vào các thành phần liên thông đã xây dựng từ các cạnh có trọng số \(< W\).

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

Ý tưởng

Với mỗi truy vấn:

1. Thêm trước tất cả các cạnh trong \(S_i\) vào DSU. Nếu ngay trong \(S_i\) đã có hai cạnh tạo thành chu trình thì trả lời NO.
2. Tiếp tục chạy thuật toán Kruskal trên các cạnh còn lại của đồ thị để hoàn thành một cây khung có trọng số nhỏ nhất chứa \(S_i\).
3. So sánh tổng trọng số của cây khung vừa tạo với trọng số của MST chuẩn của đồ thị ban đầu. Nếu bằng nhau và đủ \(N - 1\) cạnh thì in YES, ngược lại in NO.

Độ phức tạp

• Thời gian: \(O(Q \cdot M \log M)\) hoặc \(O(Q \cdot M \cdot \alpha(N))\) nếu mảng cạnh đã được sắp xếp trước.
• Không gian: \(O(N + M)\)
• Đánh giá: Quá chậm khi \(N, M, Q \leq 5 \cdot 10^5\). Chỉ phù hợp với \(N, M, Q \leq 1000\).

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

Nhận xét quan trọng

1. Theo thuật toán Kruskal, khi duyệt các cạnh theo thứ tự trọng số tăng dần:
   • Trạng thái các thành phần liên thông sau khi xét xong tất cả các cạnh có trọng số \(< W\) là cố định.
   • Một truy vấn \(S_i\) hợp lệ nếu và chỉ nếu tại mọi mức trọng số \(W\), tập các cạnh có trọng số \(W\) trong \(S_i\) khi gộp vào đồ thị hiện tại không tạo ra chu trình.
2. Ta có thể xử lý offline tất cả các truy vấn đồng thời cùng một lượt duyệt Kruskal:
   • Phân rã mỗi truy vấn \(i\) thành các nhóm cạnh nhỏ hơn theo trọng số \(W\).
   • Dùng cấu trúc DSU có thể hoàn tác (DSU with Rollback):
     • Tại mức trọng số \(W\), trước khi gộp các cạnh của đồ thị gốc có trọng số \(W\), ta lần lượt "thử" gộp các cạnh trọng số \(W\) của từng truy vấn.
     • Nếu có bất kỳ cạnh nào nối 2 đỉnh đã thuộc cùng một thành phần liên thông, truy vấn đó lập tức bị đánh dấu là NO.
     • Sau khi thử xong cho một truy vấn, ta hoàn tác (rollback) DSU về trạng thái ban đầu để kiểm tra truy vấn tiếp theo.
     • Sau khi kiểm tra xong tất cả các truy vấn ở mức \(W\), ta gộp vĩnh viễn các cạnh trọng số \(W\) của đồ thị gốc vào DSU và chuyển sang mức trọng số tiếp theo.

Cấu trúc DSU with Rollback

• Khi cài DSU có Rollback, ta không dùng nén đường đi (Path Compression) mà chỉ dùng gộp theo kích thước/độ cao (Union by Rank / Size) để đảm bảo mỗi thao tác gộp chỉ thay đổi một số lượng nhỏ biến và độ sâu cây luôn là \(O(\log N)\).
• Ta duy trì một ngăn xếp (history) lưu lại các thao tác gộp: đỉnh nào được nối vào đỉnh nào và kích thước tăng lên bao nhiêu, giúp hoàn tác trong \(O(1)\) cho mỗi thao tác.

Các bước thực hiện

1. Tiền xử lý:
   • Gom nhóm các cạnh của đồ thị gốc theo trọng số \(W\).
   • Với mỗi truy vấn \(i\), duyệt qua các cạnh trong \(S_i\) và gom nhóm chúng theo trọng số \(W\) vào danh sách query_by_weight[W][i].
2. Duyệt qua từng trọng số \(W\) từ nhỏ đến lớn:
   • Với mỗi truy vấn \(i\) có cạnh mang trọng số \(W\):
     • Lưu vị trí hiện tại của lịch sử: snapshot = history.size().
     • Lần lượt xét từng cạnh \((u, v)\) có trọng số \(W\) trong truy vấn \(i\):
       • Nếu find(u) == find(v): truy vấn \(i\) vi phạm (tạo chu trình), ta gán kết quả của truy vấn \(i\) là NO.
       • Ngược lại: gọi unite(u, v) (ghi lại thao tác vào history).
     • Thực hiện rollback DSU về lại mốc snapshot.
   • Sau khi thử xong tất cả các truy vấn ở mức \(W\), tiến hành gộp vĩnh viễn các cạnh của đồ thị gốc có trọng số \(W\) vào DSU.
3. In kết quả: Các truy vấn không bị đánh dấu NO ở bất kỳ bước nào sẽ cho kết quả là YES.

Độ phức tạp

• Thời gian:
  • Sắp xếp và phân nhóm các cạnh: \(O(M \log M + \sum k_i \log (\sum k_i))\).
  • Mỗi thao tác find, unite, rollback trên DSU with Rollback tốn \(O(\log N)\).
  • Tổng thời gian xử lý: \(O(M \log M + (M + \sum k_i) \log N)\).
  • Hoàn toàn chạy tốt trong giới hạn thời gian với \(N, M, \sum k_i \leq 5 \cdot 10^5\).
• Bộ nhớ: \(O(N + M + \sum k_i)\) để lưu danh sách cạnh, phân nhóm truy vấn và lịch sử DSU.