双栈排序[并查集]

本文主要是介绍双栈排序[并查集]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

分析 

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

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

网上有个证明(原网https://blog.csdn.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;
}

 

这篇关于双栈排序[并查集]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---