Rank of Tetris

Rank of Tetris

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

Total Submission(s): 256 Accepted Submission(s): 110

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

Author linle

Source HDOJ 2007 Summer Exercise（2）

Recommend lcy

/*
yy了一天这个题的各种想法，最后看了题解才知道是拓扑排序，又看了一下拓扑排序；

拓扑排序：将一个图入度为零的点加入队列，如果多余一个，那么这个图不是树，很可能是森林，如果只有一个节点，
就进行删根操作，每删一个根就把这个根输出，删根时也将与之关联的边删掉
*/
#include<bits/stdc++.h>
#define N 20005
using namespace std;
vector<int >v[N];//构建邻接矩阵
int bin[N];//用于构建并查集
int in[N];//用于记录每个节点的入度
int n,m,sum;//节点数
char op[N][];
void inti()
{
    sum=n;
    for(int i=;i<=n;i++)
    {
        bin[i]=i;
        v[i].clear();
        in[i]=;
    }
}
int findx(int x)
{
    while(x!=bin[x])
        x=bin[x];
    return x;
}
int judge(int x,int y)
{
    int fx=findx(x);
    int fy=findx(y);
    if(fx!=fy)
    {
        bin[fx]=fy;
        return ;
    }
    return ;
}
void topoSort()
{
    queue<int >q;
    int i;
    for(i=;i<n;i++)
        if(in[i]==&&findx(i)==i)//入度为零的点（一棵树的根节点）
            q.push(i);
    int flag=;
    while(!q.empty())
    {
        if(q.size()>)//多于一个根节点就说明信息不完整
            flag=;
        int now=q.front();
        q.pop();
        sum--;
        for(i=;i<v[now].size();i++)
            if(--in[v[now][i]]==)//删根
                q.push(v[now][i]);//删根之后的子树根节点
    }
    if(sum>)
    {
        puts("CONFLICT");
    }
    else if(flag==)
    {
        puts("UNCERTAIN");
    }
    else
    {
        puts("OK");
    }
    return;
}
int x[N],y[N];
int main()
{
    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);
    //int c=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        //if(c++==2)
        //    break;
        //cout<<"n="<<n<<" m="<<m<<endl;
        inti();
        for(int i=;i<m;i++)
        {
            scanf("%d%s%d",&x[i],op[i],&y[i]);
            //cout<<x[i]<<" "<<op[i]<<" "<<y[i]<<endl;
            if(op[i][]=='=')
            {
                if(judge(x[i],y[i]))//两点不属于同一并查集
                {
                    sum--;
                }
            }
            getchar();
        }
        //cout<<endl;
        //break;
        for(int i=;i<m;i++)
        {
            if(op[i][]!='=')
            {
                int fx=findx(x[i]);
                int fy=findx(y[i]);
                if(op[i][]=='>')
                {
                    v[fx].push_back(fy);
                    in[fy]++;
                }
                else
                {
                    v[fy].push_back(fx);
                    in[fx]++;
                }
            }

        }
        topoSort();
    }
    return ;
}