AcWing 153. 双栈排序

#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 1010;

int n;
int a[N], minv[N];
bool g[N][N];
int color[N];

bool dfs(int u, int c)
{
    color[u] = c;
    for (int v = 1; v <= n; v++)
        if (g[u][v])
        {
            if (color[v] == c) return false;
            if (color[v] == -1 && !dfs(v, !c)) return false;
        }

    return true;
}

bool isBipartite() {
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0)) {
                return false;
            }
    return true;
}

void printResult() {
    stack<int> stk1, stk2;
    int cur = 1;
    for (int i = 1; i <= n; i ++ )
    {
        if (color[i] == 0)
        {
            stk1.push(a[i]);
            cout << "a ";
        }
        else
        {
            stk2.push(a[i]);
            cout << "c ";
        }

        while (true)
        {
            if (stk1.size() && stk1.top() == cur)
            {
                stk1.pop();
                cout << "b ";
                cur++ ;
            }
            else if (stk2.size() && stk2.top() == cur)
            {
                stk2.pop();
                cout << "d ";
                cur++ ;
            }
            else break;
        }
    }
    cout << endl;
}

void sort(int a[]) {
    minv[n + 1] = n + 1;
    for (int i = n; i >= 0; i--) {
        minv[i] = min(minv[i + 1], a[i]);
    }

    memset(g, false, sizeof g);
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            if (a[i] < a[j] && minv[j + 1] < a[i])
                g[i][j] = g[j][i] = true;

    memset(color, -1, sizeof color);

    if (!isBipartite()) {
        cout << 0 << endl;
        return;
    }

    printResult();
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        sort(a);

    }

    return 0;
}