自从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 Input3 3 0 > 1 1 < 2 0 > 2 4 4 1 = 2 1 > 3 2 > 0 0 > 1 3 3 1 > 0 1 > 2 2 < 1Sample Output
OK CONFLICT UNCERTAIN
使用拓扑排序，当出现环的时候，就是信息冲突，当出现两个入度为0的点，就是信息不完整
拓扑排序：找入度为0的节点，把该节点出度的点的入度减1，然后重复过程
同时题目里还有=的情况，用并查集把等于的点视为一个点
#define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<cstdlib> #include<cmath> #include<queue> using namespace std; typedef long long ll; #define Inf 99999999 #define Maxn 10005 #define Naxn 10005 int f[Naxn], in[Naxn]; vector<int> map[Naxn]; int n, m, sum; struct Map { int a, b; char c; }temp[Maxn]; void init() { for (int i = 0; i < n; i++) { f[i] = i; } } int find(int a) { if (f[a] != a) { f[a] = find(f[a]); } return f[a]; } bool marge(int a, int b) { int x = find(a); int y = find(b); if (x != y) { f[y] = x; return true; } return false; } void topo() { int ex = 0; queue<int> que; for (int i = 0; i < n; i++) { if (in[i] == 0 && f[i] == i) { que.push(i); } } while (!que.empty()) { if (que.size() > 1) { ex = 1; } int pos = que.front(); que.pop(); for (int i = 0; i < map[pos].size(); i++) { in[map[pos][i]]--; if (in[map[pos][i]] == 0) { que.push(map[pos][i]); } } sum--; } if (sum > 0) { printf("CONFLICT\n"); } else if (ex) { printf("UNCERTAIN\n"); } else { printf("OK\n"); } } int main() { while (cin >> n >> m) { sum = n; init(); memset(map, 0, sizeof(map)); memset(in, 0, sizeof(in)); for (int i = 0; i < m; i++) { cin >> temp[i].a >> temp[i].c >> temp[i].b; if (temp[i].c == ‘=‘) { if (marge(temp[i].a, temp[i].b)) { sum--; } } } for (int i = 0; i < m; i++) { if (temp[i].c == ‘=‘) { continue; } int x = find(temp[i].a); int y = find(temp[i].b); if (temp[i].c == ‘>‘){ map[x].push_back(y); in[y]++; } else{ map[y].push_back(x); in[x]++; } } topo(); } return 0; }
原文：https://www.cnblogs.com/Vetsama/p/13332847.html