Tetris排名系统(拓扑排序与并查集的应用)

自从Lele开发了Rating系统后，他的Tetris事业如虎添翼，并迅速推广到全球。为了更好地迎合爱好者的喜好，Lele计划制作一个全球Tetris高手排行榜，定期更新，其知名度甚至超过福布斯富豪榜。排名规则是根据Rating从高到低排列，如果Rating相同，则按RP（人品值）从高到低排列。

Lele需要对N个人进行排名，编号为0到N-1，编号越大，RP越高。Lele从狗仔队那里获得了一些关于Rating的信息，这些信息可能有三种情况：“A > B”、“A = B”和“A
现在Lele想知道，根据这些信息能否确定出这个高手榜。如果可以，则输出“OK”。否则，请判断是信息不完全（输出“UNCERTAIN”），还是信息中包含冲突（输出“CONFLICT”）。注意：如果信息同时包含冲突且不完全，应输出“CONFLICT”。

本题目包含多组测试，请处理到文件结束。每组测试第一行包含两个整数N和M（0≤N≤10000, 0≤M≤20000），分别表示要排名的人数以及得到的关系数。接下来M行，分别表示这些关系。

对于每组测试，在一行里按题目要求输出。

使用并查集将名次相等的合并，保证以下操作都只用到了父节点。当存在环时（cnt != num），表示冲突；当存在多个入度为0的顶点时，条件不够。

代码：
#include
#include
#include
#define MAXN 10000 + 10
using namespace std;
int top, head[MAXN];
int in[MAXN];
int per[MAXN];
int n, m;
struct Edge { int to, next; } edge[2 * MAXN];
struct Node { int a, b; char c; };
Node node[MAXN];
void init() {
top = 0;
memset(head, -1, sizeof(head));
memset(in, 0, sizeof(in));
for (int i = 0; i }
void add(int u, int v) {
Edge E = {v, head[u]};
edge[top] = E;
head[u] = ++top;
in[v]++;
}
int find(int x) { return per[x] == x ? x : per[x] = find(per[x]); }
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) per[fy] = fx;
}
void topo() {
queue q;
int cnt = 0, num = 0, v;
bool flag = false;
for (int i = 0; i if (per[i] == i) {
++num; // 记录构图的定点个数
if (in[i] == 0) q.push(i);
}
}
if (q.size() > 1) flag = true; // 条件不够
while (!q.empty()) {
v = q.front();
q.pop();
--in[v];
++cnt; // 记录删去的顶点个数，以判断是否冲突
for (int i = head[v]; i != -1; i = edge[i].next) {
Edge E = edge[i];
if (--in[E.to] == 0) q.push(E.to);
}
if (q.size() > 1) flag = true; // 同上
}
if (cnt != num && flag) printf("CONFLICT\n");
else if (flag) printf("UNCERTAIN\n");
else if (num != cnt) printf("CONFLICT\n");
else printf("OK\n");
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 0; i scanf("%d %c %d", &node[i].a, &node[i].c, &node[i].b);
if (node[i].c == '=') merge(node[i].a, node[i].b);
}
for (int i = 0; i if (node[i].c == '=') continue;
int fa = find(node[i].a), fb = find(node[i].b);
if (node[i].c == '>') add(fa, fb);
else add(fb, fa);
}
topo();
}
}