双栈排序[并查集]

---

分析 

网上很多人用二分图染色,但是并查集来判断冲突性也是极好的

首先,单栈排序有这么一个性质

网上有个证明(原网https://blog.****.net/linwh8/article/details/52606751)

能判定之后

我们令x_1表示x放在1里面

如果存在x<y<k 使q[k]<q[x]<q[i] 也就是x,y必须放在两个栈中

我们合并x_1,y_2

如果在合并时发现x_1 y_1在一个集合,那就有冲突了

	f[n+1]=0x3fffffff;
	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[i]<a[j]&&a[i]>f[j+1]){
				int x1=find(i),x2=find(i+n),y1=find(j),y2=find(j+n);
				if(x1==y1){cout<<"0";return 0;}
				if(x2==y2){cout<<"0";return 0;}
				fa[x1]=y2,fa[x2]=y1;
			}
		} 

因为题目要求字典序最小,所以对于没有约束的点,我们把它放在第一个栈(0表示第一个栈)

有约束的点的栈是确定的

---

#include<bits/stdc++.h>
#define N 1005
using namespace std;
int fa[N*2],Belong[N];
int n,a[N],f[N],now=1;
int read(){
	int cnt=0;char ch=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
	return cnt;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	n=read();
	for(int i=1;i<=2*n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) a[i]=read();
	f[n+1]=0x3fffffff;
	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[i]<a[j]&&a[i]>f[j+1]){
				int x1=find(i),x2=find(i+n),y1=find(j),y2=find(j+n);
				if(x1==y1){cout<<"0";return 0;}
				if(x2==y2){cout<<"0";return 0;}
				fa[x1]=y2,fa[x2]=y1;
			}
		} 
	memset(Belong,-1,sizeof(Belong));
	Belong[1]=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			if(find(i)==find(j)) Belong[j]=Belong[i];
			else if(find(i+n)==find(j)||find(j+n)==find(i)) Belong[j]=Belong[i]^1;
			else if(Belong[j]==-1) Belong[j]=0;
		}
	stack<int> S1;
	stack<int> S2;
	for(int i=1;i<=n;i++){
		if(Belong[i]==0) S1.push(a[i]),cout<<"a ";
		else S2.push(a[i]),cout<<"c ";
		while((!S1.empty()&&S1.top()==now)||(!S2.empty()&&S2.top()==now)){
			if(!S1.empty()&&S1.top()==now) S1.pop(),cout<<"b ";
			else S2.pop(),cout<<"d ";now++;
		}
	}return 0;
}