hdu Rank of Tetris

Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 78 Accepted Submission(s): 35

Problem Description

自从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

Sample Output

OK
CONFLICT
UNCERTAIN

Author

linle

Source

HDOJ 2007 Summer Exercise（2）

Recommend

lcy

分析：该题为并查集和拓扑排序结合的题目。1、相等的数先用并查集合并，检查是否有不等号的数的祖先相等，如若这样，输出矛盾，返回。同时要通过重复的数对数确定不想等数的总个数。2、利用链表建立邻接表存储每个数比他大的数，同时记录下每个数比他小的数的个数。3、利用队列进行拓扑排序：若进队个数不等于不等的数的个数，则存在环不能入队，即矛盾。若某次队中含有超过一个元素，证明这些数之间无法确定大小关系关系，即无确定；其他情况OK。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 10001
#define MAXM 20001
int fa[MAXN], cnt[MAXN];
int n, m, i, num;

typedef struct S {
    int u, v, o;
} EDGE;
EDGE e[MAXM];

typedef struct S1 {
    int val;
    struct S1 *next;
} LB;
LB *lb[MAXN], temp[MAXM];

int find(int x) {
    if (x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    int fx, fy;
    fx = find(x);
    fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
        num--;
    }
}

void add(int x, int y) {
    temp[i].val = y;
    temp[i].next = lb[x];
    lb[x] = &temp[i];
    cnt[y]++;
}

int main() {
    int con, unc, a, b;
    while (scanf("%d%d", &n, &m) != EOF) {
        num = n;
        con = 0;
        unc = 0;
        for (i = 0; i < n; ++i)
            fa[i] = i;
        memset(cnt, 0, sizeof (cnt));
        for (i = 1; i <= m; ++i)
            lb[i] = NULL;
        for (i = 1; i <= m; ++i) {
            scanf("%d %c %d", &e[i].u, &e[i].o, &e[i].v);
            if (con)
                continue;
            if (e[i].o == '=') {
                merge(e[i].u, e[i].v);
            } else {
                int fa = find(e[i].u);
                int fb = find(e[i].v);
                if (fa == fb)
                    con = 1;
            }
        }
        if (con) {
            printf("CONFLICT\n");
            continue;
        }
        for (i = 1; i <= m; ++i) {
            if (e[i].o != '=') {
                a = find(e[i].u);
                b = find(e[i].v);
                if (e[i].o == '<')
                    add(a, b);
                else
                    add(b, a);
            }
        }
        queue <int> q;
        for (i = 0; i < n; ++i) {
            if (cnt[i] == 0 && i == find(i)) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            if (q.size() > 1)
                unc = 1;
            int t = q.front();
            q.pop();
            num--;
            for (; lb[t]; lb[t] = lb[t]->next) {
                if (--cnt[lb[t]->val] == 0)
                    q.push(lb[t]->val);
            }
        }
        if (num)
            printf("CONFLICT\n");
        else if (unc)
            printf("UNCERTAIN\n");
        else
            printf("OK\n");
    }
    return 0;
}