给你对于任意一个 ai,bj 的大小关系的判断,让你构造 a,b 序列满足条件。无解输出No
拓扑排序+并查集
#include <iostream> #include <cstring> #include <queue> using namespace std ; const int N=4000,M =1e6+3; #define int long long int n,m, in[N],fa[N],D[N]; int nxt[M],go[M],hd[N],all; void add_(int x,int y){ go[++all]=y,nxt[all]=hd[x]; hd[x]=all; } int find(int x){ return x==fa[x]? x:fa[x]=find(fa[x]); } void cmb(int i,int j){ int fx= find(i), fy=find(j); fa[fy]=fx; } void Topo(){ int i,x,Sum=0,num=0; queue<int> q; for(i=1;i<=n+m;i++){ int fx=find(i);if(fx!=i)continue; if(in[i]==0){ q.push(i); D[i]=1; } ++Sum; } while(q.empty()==0){ x=q.front(); q.pop(); num++; for(i=hd[x];i;i=nxt[i]){ int y=go[i]; D[y]=max(D[y],D[x]+1); if(--in[y]==0) q.push(y); } } if(Sum==num){ cout<<"Yes\n"; for(i=1;i<=n;i++) cout<<D[find(i)]<<' '; cout<<endl; for(i=n+1;i<=n+m;i++) cout<<D[find(i)]<<' '; } else{ cout<<"No\n"; } } char op[N][N]; signed main(){ char c; cin>>n>>m; for(int i=1;i<=n+m;i++) fa[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>op[i][j]; c=op[i][j]; if(c=='=') cmb(i,n+j); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(op[i][j]=='<') in[find(j+n)]++,add_(find(i),find(j+n)); if(op[i][j]=='>') in[find(i)]++,add_(find(j+n),find(i)); } Topo() ; }
标签:fa,Gourmet,void,CF1131D,choice,int,include,find,hd From: https://www.cnblogs.com/towboa/p/17264719.html