Hướng làm đơn thuần nhất của bài toán này là như sau:
+ Duy trì các vùng màu bằng cấu trúc DSU;
+ Với mỗi thao tác tô màu, ta duyệt qua mọi vùng màu kề với vùng được tô, mà cùng màu với nó, rồi
$\texttt{union}$ lại trên DSU.
Tuy nhiên, trong trường hợp tệ nhất, ta phải duyệt qua **mọi** vùng màu trên bảng (ví dụ khi có
một vùng to được bao quanh bởi các vùng nhỏ), khi đó độ phức tạp thổi phồng lên
$\mathcal{O}(n \times m)$ mỗi thao tác.
Cách tối ưu là chia căn trên các tập nặng nhẹ. Ta gọi một vùng màu là **nặng** nếu số vùng màu kề
với nó lớn hơn $B$ xác định trước, và nhẹ nếu ngược lại. Như thường lệ, xử lý vùng nhẹ có thể thực
hiện trâu như trên, nhưng vùng nặng lại khó khăn hơn.
Do số lượng vùng kề tỉ lệ thuận với kích thước của một vùng màu, nên sẽ luôn có không quá
$\mathcal{O}(\frac{n \times m}{B})$ vùng nặng. Vậy với mỗi vùng, ta lưu riêng các vùng kề **nặng**
của nó. Ngoài ra, với mỗi vùng nặng, ta cũng sẽ lưu các vùng kề nhẹ của nó, nhóm lại theo màu.
Tổng quan thuật toán có thể được mô tả bằng các thủ tục sau:
+ $\texttt{color}(u, c)$ tô màu vùng $u$ bởi màu $c$: Gọi $\texttt{neighbors}(u, c)$, và với mỗi
$v$ được trả về, gọi $\texttt{union}(u, v)$.
+ $\texttt{neighbors}(u, c)$ trả về tất cả các vùng kề với $u$ mà có màu $c$:
+ Nếu $u$ là vùng nhẹ thì ta chỉ cần duyệt hết các vùng kề của nó rồi kiểm tra;
+ Ngược lại, ta dùng đúng danh sách các vùng kề nhẹ ở trên mà đã xếp theo màu, kết hợp với
duyệt tất cả các vùng nặng kề. Nhận thấy rằng danh sách vùng kề nhẹ với màu này có thể được
clear luôn, do theo cách gọi ở trên, chúng sẽ được kết hợp thành một vùng ngay.
+ $\texttt{union}(u, v)$ kết hợp hai vùng $u$ và $v$: Ta cần kết hợp danh sách các vùng kề và vùng
kề nặng của $u$ và $v$ lại; nếu có một trong hai vùng là nặng, hoặc sau khi kết hợp có vùng trở nên
nặng thì ta cũng kết hợp danh sách các vùng kề nhẹ của nó. Điều này có thể thực hiện bằng kỹ thuật
small-to-large.
Chi tiết cài đặt xin nhường lại cho bạn đọc.
## Độ phức tạp thời gian
+ Với hàm $\texttt{neighbors}$, tổng thời gian với các lần gọi $u$ nhẹ là $\mathcal{O}(q \times B)$;
còn với các lần $u$ nặng thì tổng cộng là $\mathcal{O}(q\times \frac{n\times m}{B})$.
+ Số lần gọi hàm $\texttt{union}$ là $\mathcal{O}(n \times m)$, nên tổng thời gian của nó là
$\mathcal{O}(n \times m \times \log(n \times m))$.
Chọn $B=\sqrt{n\times m}$ sẽ cho ra độ phức tạp tối ưu.
tuongll
Created at
0 likes