Dựng một đồ thị ~2~ phía, ~2 \times 10^5~ đỉnh bên trái sẽ tương ứng cho các hàng, tương tự, ~2 \times 10^5~ đỉnh bên phải sẽ tương ứng cho các cột. ~2~ đỉnh bất kì ở ~2~ phía sẽ có cạnh nối khi và chỉ khi có một quân xe ở vị trí tương ứng.

Nhận xét: nếu đồ thị tạo ra được chu trình, thì tập hợp các quân xe trong chu trình đó sẽ phải cùng ở lại hoặc cùng bị gỡ bỏ. Còn nếu không phải là chu trình, các quân xe đó sẽ bị loại bỏ vì đỉnh nối các quân xe đó sẽ có bậc là ~1~ đồng nghĩa với việc hàng/cột đó sẽ bị thống trị.

Vì bậc của mỗi đỉnh trong đồ thị không quá ~2~ nên ta sử dụng ~DFS~ để đếm số chu trình trong ~O(N)~

Đáp án bài toán sẽ là: ~2^k~ với ~k~ là số chu trình.

Độ phức tạp: ~O(N)~