HDU 1811 Rank of Tetris 拓补排序+并查集

Rank of Tetris

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

【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
> 1
< 2
> 2
4
= 2
> 3
> 0
> 1
3
> 0
> 2
< 1
【Sample Output】

OK
CONFLICT
UNCERTAIN
【题意】

给定一些点对之间的关系（大于小于相等），判断是否发生冲突。

【分析】

对于冲突判断，直观的想法就是拓扑排序。以大于号或者小于号方向作为拓扑序的方向，如果处理时出现违反拓扑序列的情况则可判断为冲突。

然后这道题还有另外一个问题就是相等情况的处理，如果直接按照拓扑排序对其进行分析，则可能发生错误。为了解决这个问题，可以用并查集进行预处理，将所有相等的点缩成1个点，然后进行后序的拓扑排序。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int father[10001]; 

void clean_father(int n)
{
    for (int i=0;i<n;i++) father[i]=i;
} 

int getfather(int x)
{
    if (father[x]!=x) father[x]=getfather(father[x]);
    return father[x];
}

void link(int x,int y)
{
    father[getfather(x)]=getfather(y);
} 

int x[20001],y[20001],rd[10001],num[10001],start[10001];
char z[20001];

typedef struct {
    int a,b;
} node;
node a[20001];

bool op(node a,node b)
{
    return a.a<b.a;
}

int stack[10001];

int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        clean_father(n);
        
        for (int i=1;i<=m;i++)
        {
            scanf("%d %c %d",&x[i],&z[i],&y[i]);
            if (z[i]=='=') link(x[i],y[i]);
        }
        
        int tail=0;
        for (int i=0;i<n;i++) rd[i]=-1;
        int tot=0;
        for (int i=0;i<n;i++) 
        {
            rd[getfather(i)]=0;
            if (rd[i]==0) tot++;
        }
        for (int i=1;i<=m;i++)
        switch(z[i])
        {
            case '>':
                tail++;
                a[tail].a=getfather(x[i]);
                a[tail].b=getfather(y[i]);
                rd[getfather(y[i])]++;
                break;
            case '<':
                tail++;
                a[tail].a=getfather(y[i]);
                a[tail].b=getfather(x[i]);
                rd[getfather(x[i])]++;
        }
        sort(&a[1],&a[tail+1],op);
        
        int o=-1;
        for (int i=0;i<n;i++) num[i]=0;
        for (int i=1;i<=tail;i++)
        {
            if (a[i].a!=o)
            {
                o=a[i].a;
                start[o]=i;
            }
            num[o]++;
        }
        
        int top=0;
        for (int i=0;i<n;i++)
        if (rd[i]==0)
        {
            top++;
            stack[top]=i;
        }
        
        if (top==0)
        {
            printf("CONFLICT
");
            continue;
        }
        
        bool flag=false,done=false;
        while (top>0&&(!done))
        {
            if (top>1) flag=true;
            int now=stack[top];
            top--;tot--;
            for (int i=0;i<num[now];i++)
            {
                rd[a[start[now]+i].b]--;
                if (rd[a[start[now]+i].b]==0) 
                {
                    top++;
                    stack[top]=a[start[now]+i].b;
                } else
                if (rd[a[start[now]+i].b]<0)
                {
                    done=true;
                    break;
                }
            }
            num[now]=0;
        }
        if (tot>0||done) printf("CONFLICT
");
        else if (flag) printf("UNCERTAIN
");
        else printf("OK
");
    }
    
    return 0;
}

View Code

Do Cool Things That Matter!