并查集+拓扑排序
#include<iostream> #include<vector> #include<queue> #define maxn 20005 using namespace std; int n,m; vector<int>g[maxn]; int head[maxn]; struct stu { int a,b; string c; }; stu mapp[maxn]; int f[maxn]; void init() { for(int i=0;i<maxn;i++) f[i]=i,g[i].clear(),head[i]=0; } int dfs(int x) { if(f[x]!=x) f[x]=dfs(f[x]); return f[x]; } void merge(int x,int y) { int rx=dfs(x); int ry=dfs(y); if(rx!=ry) f[ry]=rx; } int add(int x,int y) { g[x].push_back(y); head[y]++; } void topo() { queue<int>root; int flag=0; for(int i=0;i<n;i++) { if(f[i]==i&&!head[i]) root.push(dfs(i)); } int re=0; while(root.size()) { int x=root.front(); root.pop(); if(root.size()!=0) flag=1; re++; head[x]--; for(int i=0;i<g[x].size();i++) { head[g[x][i]]--; if(!head[g[x][i]]) root.push(g[x][i]); } } for(int i=0;i<n;i++) if(f[i]!=i) re++; if(re!=n) { cout<<"CONFLICT"<<endl; return; } if(flag==1) { cout<<"UNCERTAIN"<<endl; return; } cout<<"OK"<<endl; } int main() { cin.sync_with_stdio(false); while(cin>>n>>m) { init(); int flag=0; for(int i=0;i<m;i++) { cin>>mapp[i].a>>mapp[i].c>>mapp[i].b; if(mapp[i].c=="=") merge(mapp[i].a,mapp[i].b); } for(int i=0;i<m;i++) { mapp[i].a=dfs(mapp[i].a); mapp[i].b=dfs(mapp[i].b); if(mapp[i].c=="=") continue; if(mapp[i].b==mapp[i].a) flag=1; if(mapp[i].c=="<") add(mapp[i].a,mapp[i].b); else add(mapp[i].b,mapp[i].a); } if(flag) cout<<"CONFLICT"<<endl; else topo(); } return 0; }