题目：
题目链接：LUOGU P1155 双栈排序
题解：
按单栈的规则建图，如果不能再同一个栈就连边，所以总共分成三种情况：
1.单栈直接就可以解决的
2.双栈排序连成二分图才能解决
3.双栈排序时连不成二分图，无解
在建二分图的时候，运用二分图染色，把图染成黑白两种色，这样用来表示二分图，然后判断是否是二分图即可，最后输出答案的时候进行对栈的模拟即可。
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int ocean=1010;
const int sea=1010;
int n,a[sea],v[sea],f[sea],g[sea][sea],q1[sea],q2[sea],head,tail,top1,top2;
void dfs(int x,int y)//二分图的dfs染色
{
v[x]=y;for(int i=1;i<=n;i++)if(g[x][i]) if(v[i]==y) {
puts("0"),exit(0);}else if(!v[i]) dfs(i,y^1);
}
int main()
{
n=read(); f[n+1]=ocean;for(int i=1;i<=n;i++) a[i]=read(); //单栈for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]);for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)if(a[j]>a[i]&&a[i]>f[j]) g[i][j]=g[j][i]=1;//dfs染色for(int i=1;i<=n;i++) if(!v[i]) dfs(i,2);//栈模拟head=tail=1; top1=top2=0;a[0]=ocean;while(tail<=n){
if(v[head]==2&&a[q1[top1]]>a[head]) printf("a "),q1[++top1]=head++;else if(tail==a[q1[top1]]) printf("b "),top1--,tail++; else if(v[head]==3&&a[q2[top2]]>a[head]) printf("c "),q2[++top2]=head++;else if(tail==a[q2[top2]]) printf("d "),top2--,tail++; }return 0;
}