Truy vấn kiểm tra có thể nối hộp thành hình tròn không C++

Cho N hộp xếp thành vòng tròn (đánh số 1..N). Có Q truy vấn, mỗi truy vấn muốn nối hộp i và j bằng một que. Điều kiện: các que không được cắt nhau, và mỗi hộp chỉ được nối tối đa 1 que. Xác định từng truy vấn có thể thực hiện được không.

Ví dụ

N = 5, Q = 2
Query 1: 3-1 → Possible
Query 2: 5-4 → Possible

Thuật toán

Mô hình hóa: Mỗi hộp là một đỉnh trên đường tròn. Nối i-j là vẽ dây cung. Hai dây cắt nhau ⇔ 4 đầu mút xen kẽ nhau trên vòng tròn (a < c < b < d theo thứ tự vòng tròn).

Dùng mảng match[i] = hộp đang nối với i (0 nếu chưa nối).

Kiểm tra truy vấn (u, v):

1. Nếu u == v hoặc match[u] != 0 hoặc match[v] != 0 → Not Possible.
2. Đảm bảo u < v (hoán đổi nếu cần).
3. Kiểm tra cắt với các cặp đã nối:
   • Với mỗi i từ 1 đến u-1: nếu match[i] nằm giữa u và v (tức u < match[i] < v) → cắt nhau.
   • Với mỗi i từ u+1 đến v-1: nếu v → cắt nhau.
4. Nếu không cắt: match[u]=v, match[v]=u → Possible.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

void solveQueries(int n, int q, vector& u, vector& v) {
    vector match(n + 1, 0);
    for (int k = 0; k < q; k++) {
        int a = u[k], b = v[k];
        bool ok = true;
        
        if (a == b || match[a] || match[b]) ok = false;
        else {
            if (a > b) swap(a, b);
            // Kiểm tra cắt với các cặp đã nối
            for (int i = 1; i < a && ok; i++) {
                if (match[i] && a < match[i] && match[i] < b) ok = false;
            }
            for (int i = a + 1; i < b && ok; i++) {
                if (match[i] && match[i] > b) ok = false;
            }
        }
        
        if (ok) {
            cout << "Possible\n";
            match[a] = b;
            match[b] = a;
        } else {
            cout << "Not Possible\n";
        }
    }
}

int main() {
    int n = 5, q = 2;
    vector u = {3, 5}, v = {1, 4};
    solveQueries(n, q, u, v);
    return 0;
}

Kết quả

Possible
Possible

Độ phức tạp

O(N) mỗi truy vấn. N, Q ≤ 1000 thì đủ nhanh. Với N, Q lớn cần cấu trúc dữ liệu phức tạp hơn (Fenwick tree +Ordered set).