每日一题【二分图染色】

每日一题【二分图染色】

题意：
给两个栈和一个排列
每次可以选择序列的第一个数入任何一个栈
或者让任一一个栈顶元素出栈
要求出栈顺序为1-n

思路：首先如果我们只有一个栈会要怎么做，2，3，1不是怎么入栈都不行吗？
那么我们可以考虑a[k]<a[i]<a[j] k<i<j,此时我们利用另一个栈来解决问题，
模拟的话感觉有点麻烦，是不是有更优的做法？
我们遇到这样a[i]<a[j]矛盾之后我们就把他们分两侧，之后还要判断是不是有冲突，类似奇数环的话就不行，这不就是二分图染色吗？染完色模拟输出就行🤷‍♂️

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>p;
const int N=1e6+5;
const int M=1e3+5;
const int mod=998244353;
int T,n,m;
int a[N], suff[N];
vector<int>G[N];
int col[N];
int dfs(int u,int c) {
    col[u]=c;
    for(auto v:G[u]) {
        if(col[v]==c)return 0;
        if(col[v]==-1&&!dfs(v,c^1))return 0;
    }
    return 1;
}

int main() {
    cin>>n;
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    suff[n+1]=mod;
    for(int i=n; i>=1; i--)suff[i]=min(a[i],suff[i+1]),col[i]=-1;
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(a[i]<a[j]&&suff[j+1]<a[i]) {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(col[i]==-1&&!dfs(i,0)) {
            printf("0\n");
            return 0;
        }
    }
    string ans="";
    int now=1;
    stack<int>s1,s2;
    for(int i=1; i<=n; i++) {
        if(col[i]==0)
            s1.push(a[i]),ans+="a ";
        else s2.push(a[i]),ans+="c ";
        while(true) {
            if(!s1.empty()&&s1.top()==now)s1.pop(),ans+="b ";
            else if(!s2.empty()&&s2.top()==now)s2.pop(),ans+="d ";
            else break;
            now++;
        }
    }
    cout<<ans<<endl;
}