Với mỗi màu, ta tạo 1 đồ thị chỉ chứa những cạnh mang màu đó, từ đó có thể dễ dàng xác định xem 2 đỉnh ~A~, ~B~ có liên thông với nhau mà chỉ sử dụng những cạnh mang màu ta đang xét hay không, bằng DSU chẳng hạn.

Với mỗi đỉnh, ta có thể đếm được số lượng màu khác nhau của những cạnh kết nối trực tiếp với nó, gọi là ~deg()~. Ở truy vấn 2 đỉnh ~A~, ~B~, giả sử ~deg(A) < deg(B)~, ta sẽ lần lượt duyệt qua từng màu trong ~deg(A)~ đó rồi kiểm tra ~A~, ~B~ có được kết nối với nhau thông qua các cạnh màu đó hay không và lưu lại đáp án của truy vấn này cho những lần sau nếu có xuất hiện truy vấn tương tự.

Từ đó ta có thuật toán ~O(m log m\sqrt{q})~.

Bởi vì với mỗi truy vấn, độ phức tạp là ~O(deg(A)logm)~. Trường hợp tệ nhất sẽ là, các truy vấn sẽ tập trung vào những đỉnh có ~deg()~ nhiều nhất, hay các cặp trong ~\sqrt{q}~ đỉnh có ~deg()~ lớn nhất, gọi ~deg()~ của các đỉnh đó là ~d_1, d_2, d_3, \cdots, d_k~ với ~k = \sqrt{q}~.

Vậy thì với mỗi đỉnh ~B~ trong tập, giả thử là đỉnh thứ i, tổng độ phức tạp sẽ là ~O((d_1 + d_2 + ... + d_{i - 1}) log m) \leq O((d_1 + d_2 + d_3 + ... + d_k) log m)~.

Tổng lại mọi đỉnh ~B~ có thể trong tập thì độ phức tạp sẽ là ~O(\sqrt{q}(d_1 + d_2 + d_3 + ... + d_k) log m)~ hay ~O(\sqrt{q}mlogm)~.

Ta có thể giảm bớt ~logm~ bằng nhiều cách như sử dụng unordered_map hay DSU.

Code tham khảo