根据题单的提示，这是一道拓补排序+并查集的题目，然而我并不会拓补排序......所以这里先写一下拓补排序相关的东西吧......
首先，拓补排序是对一系列有先后顺序的“活动”的排序。何为“有先后顺序的‘活动’”？举个例子，假如现在某人要穿衣服，那他必须要先穿内衣再穿中间的毛衣，最后再穿外套。拓补排序就是使用有向无环图(DAG)来对这些有先后顺序的活动进行排序，得到一个可行的顺序。对于同一系列的活动，可能有多于一种顺序可以使他们满足拓补排序。这跟穿衣服时可以先穿裤子再穿毛衣然后再穿外套，也可以先穿毛衣再穿裤子然后穿外套是一样的。
拓补排序的实现：先找出入度为0的点，然后将这个点以及与这个点相连的边删除，并将与这个点直接相连的点的入度都减一。再找出当前入度为0的点，重复上述过程.......当所有点的入度都为0时，说明所有的点都已经被安排了一个拓补序，拓补排序完成。如果不能使所有点的入度都为0，则可以判断当前这个图不是DAG。因此，拓补排序还可以用来判断一个有向图是否有环
具体到这道题。思路是，对于rating相等的两个点，比如说a和b，因为它们之间的序号一定不一样，所以两者之间一定能够连接一条有向边。可是如果接下来又出现了一个b = c呢？那b和c之间也要连一条有向边。不仅如此，a和c之间也要连一条有向边。所以如果出现了a = b = c = d = e = ...的情况，这个图就会很复杂。所以我们可以用并查集将那些rating相等的点都连接起来，然后将他们的根节点作为他们的代表元素，即将这些点看成是一个点。然后再用拓补排序判一下环即可。
需要注意的细节是，如果之前已经出现了a = b，往后可能会出现a > b或者a < b，这是要判断为CONFLICT
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e4+5;
int n,m;
//n个点，m条边
//将'='的点用并查集聚合为一个点
int pre[2*maxn];
int head[2*maxn];
int deg[2*maxn]; //记录每个点的入度
int tot;
struct edge{
int to;
int next;
};
edge edges[2*maxn];
void init()
{
tot=0;
for(int i=0;i<n;i++)
pre[i]=i;
mst(head,-1);mst(deg,0);
}
void add_edge(int u,int v)
{
edges[tot].to=v;
edges[tot].next=head[u];
head[u]=tot++;
deg[v]++;
}
int findr(int x)
{
if(x==pre[x])
return x;
return pre[x]=findr(pre[x]);
}
int topo()
{
queue<int> que;
int root_cnt=0;
int in_que_cnt=0;
bool flag=1;
for(int i=0;i<n;i++)
{
if(pre[i]==i){
root_cnt++;
if(deg[i]==0)
que.push(i);
}
}
while(!que.empty())
{
if(que.size()>1)
flag=0;
in_que_cnt++;
int fro=que.front();
que.pop();
for(int i=head[fro];i!=-1;i=edges[i].next)
{
int tmp=findr(edges[i].to);
deg[tmp]--;
if(deg[tmp]==0)
que.push(tmp); //为什么这里不需要将入队次数++?
}
}
if(in_que_cnt<root_cnt)
return 1; //冲突(有环)
else if(!flag)
return -1; //不可确定关系
else
return 0; //ok
}
int a[maxn],b[maxn],ch[maxn];
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
init();
getchar();
for(int i=0;i<m;i++)
{
scanf("%d %c %d",&a[i],&ch[i],&b[i]);
getchar();
if(ch[i]=='='){
int fa=findr(a[i]);
int fb=findr(b[i]);
if(fa!=fb) //若rating相等，则合并，因为a和b的序号
//一定不一致，绝对可以比出大小
pre[fa]=fb;
}
}
int ans=0;
for(int i=0;i<m;i++)
{
int fa=findr(a[i]);
int fb=findr(b[i]);
if(ch[i]!='='&&fa==fb){
ans=1;
break;
}
if(ch[i]=='<'){ //a < b
add_edge(findr(b[i]),findr(a[i]));
}else if(ch[i]=='>'){
add_edge(findr(a[i]),findr(b[i]));
}
}
if(ans==0)
ans=topo();
if(ans==1)
cout<<"CONFLICT"<<endl;
else if(ans==-1)
cout<<"UNCERTAIN"<<endl;
else
cout<<"OK"<<endl;
}
return 0;
}