自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。
为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排。
终于，Lele要开始行动了，对N个人进行排名。为了方便起见，每个人都已经被编号，分别从0到N-1,并且编号越大，RP就越高。
同时Lele从狗仔队里取得一些（M个）关于Rating的信息。这些信息可能有三种情况，分别是"A > B","A = B","A < B"，分别表示A的Rating高于B,等于B,小于B。
现在Lele并不是让你来帮他制作这个高手榜，他只是想知道，根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。
注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。
Input
本题目包含多组测试，请处理到文件结束。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系
Output
对于每组测试，在一行里按题目要求输出
Sample Input
3 3
0 > 1
1 < 2
0 > 2
4 4
1 = 2
1 > 3
2 > 0
0 > 1
3 3
1 > 0
1 > 2
2 < 1
Sample Output
OK
CONFLICT
UNCERTAIN
用并查集将Rating相同的人缩成一个点。然后拓扑排序跑一发即可。
Code
/**
* hdu
* Problem#1811
* Accepted
* Time:93ms
* Memory:2064k
*/
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <stack>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
const signed int inf = (signed)((1u << ) - );
const double eps = 1e-;
const int binary_limit = ;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
template<typename T>
inline boolean readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
return true;
} ///map template starts
typedef class Edge{
public:
int end;
int next;
Edge(const int end = , const int next = ):end(end), next(next){}
}Edge; typedef class MapManager{
public:
int ce;
int *h;
Edge *edge;
MapManager(){}
MapManager(int points, int limit):ce(){
h = new int[(const int)(points + )];
edge = new Edge[(const int)(limit + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end){
edge[++ce] = Edge(end, h[from]);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end){
addEdge(from, end);
addEdge(end, from);
}
Edge& operator [] (int pos) {
return edge[pos];
}
inline void clear() {
delete[] edge;
delete[] h;
}
}MapManager;
#define m_begin(g, i) (g).h[(i)]
///map template ends typedef class union_found{
public:
int *f;
union_found():f(NULL) {}
union_found(int points) {
f = new int[(const int)(points + )];
for(int i = ; i <= points; i++)
f[i] = i;
}
int find(int x) {
if(f[x] != x) return f[x] = find(f[x]);
return f[x];
}
void unit(int fa, int so) {
int ffa = find(fa);
int fso = find(so);
f[fso] = ffa;
}
boolean connected(int a, int b) {
return find(a) == find(b);
}
inline void clear() {
delete[] f;
}
}union_found; typedef class Rank {
public:
int id;
int dep; boolean operator < (Rank b) const {
return dep < b.dep;
}
}Rank; int n, m;
MapManager g;
int* dag;
Rank* rs;
union_found uf;
vector<Edge> rss; inline boolean init() {
if(!readInteger(n)) return false;
readInteger(m);
g = MapManager(n, m);
uf = union_found(n);
dag = new int[(n + )];
rs = new Rank[(n + )];
memset(dag, , sizeof(int) * (n + ));
char opt;
for(int i = , a, b; i <= m; i++) {
readInteger(a);
getchar();
opt = getchar();
readInteger(b);
if(opt == '>')
rss.push_back((Edge) {b, a});
else if(opt == '<')
rss.push_back((Edge) {a, b});
else if(opt == '=')
uf.unit(a, b);
}
for(int i = , a, b; i < (signed)rss.size(); i++) {
a = uf.find(rss[i].end);
b = uf.find(rss[i].next);
g.addEdge(a, b);
dag[b]++;
}
return true;
} queue<int> que;
inline void topu() {
for(int i = ; i < n; i++) {
rs[i].id = i;
rs[i].dep = ;
if(!dag[i] && uf.find(i) == i)
que.push(i);
}
while(!que.empty()) {
int e = que.front();
que.pop();
for(int i = m_begin(g, e); i; i = g[i].next) {
int& eu = g[i].end;
dag[eu]--;
smax(rs[eu].dep, rs[e].dep + );
if(!dag[eu])
que.push(eu);
}
}
} boolean* vis;
inline void solve() {
topu();
for(int i = ; i < n; i++)
if(dag[i]) {
puts("CONFLICT");
return;
}
vis = new boolean[n + ];
memset(vis, false, sizeof(boolean) * (n + ));
for(int i = ; i < n; i++) {
if(uf.find(i) == i) {
if(vis[rs[i].dep]) {
puts("UNCERTAIN");
return;
}
vis[rs[i].dep] = true;
}
}
puts("OK");
} inline void clear() {
g.clear();
uf.clear();
rss.clear();
delete[] dag;
delete[] rs;
} int main() {
while(init()) {
solve();
clear();
}
return ;
}