题意：略
分析：排序先按rating，若相同，则按rp。考虑到每个人的rp均不同，所以rating相同的人必然可以排序。那么只需要考虑rating不同的集合了。
大小关系可以用有向边表示，而大小关系的传递可以用拓扑排序来呈现。
接着就要分析，三种结果对应的情况了。
很明显，ok要求拓扑出来的必须是一条链，一旦有分支，分支处的两个（或多个）点的大小关系就不明确，也就是条件不足=>uncertain。
而矛盾conflict有两种情况：1、更改关系0=1,0>1；2、自相矛盾，即成环，0>1,0<1。
注意：在条件不足和矛盾同时发生时，要求输出的是矛盾conflict。
这里要注意，拓扑排序是可以判环的：只要完成拓扑后，发现还有点没有加入队列，那么就说明他们之间成环。若不成环，必然可以把所有点加入队列。
学习了vector的find函数
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=; struct Edge{
int x,y;
char op;
}edge[MAXN<<]; vector<int>G[MAXN];
queue<int>q;
int in[MAXN],f[MAXN];
int inq[MAXN]; void init(int n)
{
for(int i=;i<n;i++)
f[i]=i; memset(in,,sizeof(in)); for(int i=;i<n;i++)
G[i].clear();
} int Find(int x)
{
return f[x]==x?x:f[x]=Find(f[x]);
} int top(int n)
{
int flog=;
while(!q.empty())
q.pop();
memset(inq,,sizeof(inq));//判入队 for(int i=;i<n;i++)
{
int x=Find(i);
if(x!=i)//忽略所有集合中除根以外的点
inq[i]=;
else if(in[x]==){
q.push(x);
inq[x]=;
}
}
if(q.empty())//队空，成环，冲突
return -;
while(!q.empty())
{
if(q.size()>=)//多叉，不分先后，条件不足
flog=; int u=q.front();q.pop();
int sz=G[u].size();
for(int i=;i<sz;i++)
{
int v=G[u][i];
in[v]--;
if(in[v]==){
if(inq[v])//成环，冲突
return -;
else {
q.push(v);
inq[v]=;
}
}
}
}
for(int i=;i<n;i++)
if(!inq[i])//不能全部拓扑，成环，冲突
return -;
return flog;
} int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int flog=;
init(n);
for(int i=;i<m;i++)
{
scanf("%d %c %d",&edge[i].x,&edge[i].op,&edge[i].y);
if(edge[i].op=='='){
int a=Find(edge[i].x);
int b=Find(edge[i].y);
f[a]=b;
}
}
for(int i=;i<m;i++)
{
if(edge[i].op=='=')
continue; int a=Find(edge[i].x);//所有处理都是对集合的根做操作
int b=Find(edge[i].y);
if(a==b)
flog=-;
if(flog==-)
break; if(edge[i].op=='<'){
if(find(G[b].begin(),G[b].end(),a)==G[b].end()){//去重，长知识了
G[b].push_back(a);
in[a]++;
}
}else{
if(find(G[a].begin(),G[a].end(),b)==G[a].end()){
G[a].push_back(b);
in[b]++;
}
}
}
if(flog==-){
printf("CONFLICT\n");
continue;
}
flog=top(n);
if(flog==-)
printf("CONFLICT\n");
else if(flog==)
printf("UNCERTAIN\n");
else
printf("OK\n");
}
return ;
}
/*
4 3
0 < 1
1 < 2
2 < 0 4 3
0 > 1
1 < 2
0 > 2 4 3
1 = 2
0 < 1
3 > 2 4 3
1 = 2
0 < 1
0 > 2 3 3
1 = 2
2 = 0
1 > 2 3 1
1 < 2
*/