#include<stdio.h> #include<string.h>#include<queue>#include<vector>using namespace std;int f[10010],in[10010];vector<int> qu[10010];int n,m,tot;int find(int i){if(f[i]==i) return i;return f[i]=find(f[i]);}void unio(int pa,int pb){ f[pa] = pb; return;}int topo(){queue<int> q;int i,ok=0,nu,tk;for(i=0;i<n;++i){if(in[i]==0&&f[i]==i) q.push(i);}while(!q.empty()){if(q.size()>1) ok=1 ;//条件不足 int temp=q.front();q.pop();tot–; nu=qu[temp].size();for(i=0;i<nu;++i){tk=qu[temp][i];//qu[temp].pop_back();in[tk]–;if(!in[tk]) q.push(tk);}} if(tot>0) ok=2;return ok;}int a[10010],b[10010];char ch[10010];int main(){while(~scanf("%d%d",&n,&m)){tot=n;int pa,pb,ok=0;memset(qu,0,sizeof(qu));memset(in,0,sizeof(in));for(int i=0;i<=n;++i){f[i]=i;//qu[i].clear();}for(int i=0;i<m;++i){scanf("%d %c %d",&a[i],&ch[i],&b[i]);//printf("%d#%c#%d\n",a,ch,b);pa=find(a[i]);pb=find(b[i]);if(ch[i]=='='&&pa!=pb) unio(pa,pb),tot–;/* //之前写成了这样，把合并及> ,< 的 判断同时进行的，在此处WA了n遍！！！if(ch[i]=='='&&pa!=pb) unio(pa,pb),tot–;if(ch[i]=='>')qu[pb].push_back(pa),in[pa]++;if(ch[i]=='<') qu[pa].push_back(pb),in[pb]++;*/ 要一次性的把所有的相等节点先合并 } for(int i=0;i<m;++i){pa=find(a[i]);pb=find(b[i]);if(ch[i]=='>')qu[pb].push_back(pa),in[pa]++;if(ch[i]=='<')qu[pa].push_back(pb),in[pb]++;}ok=topo();if(ok==2) printf("CONFLICT\n");else if(ok==1) printf("UNCERTAIN\n");else printf("OK\n");}return 0;}
先把相等的点利用并查集合并，，然后进行拓扑排序
地球仍然转重，世间依旧善变，而我永远爱你。
