相等的用并查集处理
剩下的部分就拓扑排序 这里是用队列写的
若所有点都有正确的大小关系顺序 就合法 否则conflict
其次一个点对应多个下一级 就不确定
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int r[10005],num,x[20005],y[20005],in[10005]; char op[20005][3]; vector q[10005]; int root(int a) { if(r[a]==a) return a; r[a]=root(r[a]); return r[a]; } void merge(int a,int b) { int ra,rb; ra=root(a); rb=root(b); if(ra==rb) return ; num--; if(rb>ra) { r[ra]=rb; } else r[rb]=ra; } int main() { int n,m,i,tmp; while(~scanf("%d%d",&n,&m)) { for(i=0;i<=n;i++) r[i]=i,q[i].clear(); memset(in,0,sizeof in); num=n; for(i=0;i ') { q[xx].push_back(yy); in[yy]++; } else if(op[i][0]=='<') { q[yy].push_back(xx); in[xx]++; } } queue qq; for(i=0;i 1) flag=1; int tmp=qq.front(); qq.pop(); num--; for(i=0;i 0) printf("CONFLICT\n"); else if(flag) printf("UNCERTAIN\n"); else printf("OK\n"); } return 0; }