Rank of Tetris

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1811

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

题解

这题首先肯定是处理“＝”，就用并查集缩点即可。

然后题目就变成了：给你一个有向图判断是否是无环图，并判段是否存在一条路径经过所有点。

判环我只会用tarjian，然后怎么判结果是否唯一，我就不会了。

上网查了查，原来用拓扑排序，我来讲下大概思路：

就是先将入度为零的点加入一个队列，然后每次pop队列中一个点(记作x)，然后将它所连接的点（记作y）入度减一，如果y的入度变为零，就将y也入队，直到队列为空。

如果队列存在环，那么一环上的点都不会入队，所以他们的入度一直大于零；如果中途队列中元素多余一个，说明这些元素互不影响，则答案不唯一；如果前面两条都不满足，则答案唯一。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 10050

#define M 20050

int n,m,tot,last[N];

struct Edge{int x,y,s;}edges[M];

template<typename T>void read(T&x)

{

    ll k=0; char c=getchar();

    x=0;

    while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();

    if (c==EOF)exit(0);

    while(isdigit(c))x=x*10+c-'0',c=getchar();

    x=k?-x:x;

}

void read_char(char &c){while((c=getchar())!='<'&&c!='>'&&c!='='&&c!=EOF);}

void AddEdge(int x,int y){edges[++tot]=Edge{x,y,last[x]};last[x]=tot;}

int find(int *fa,int x){return x==fa[x]?x:fa[x]=find(fa,fa[x]);}

bool merge(int *fa,int x,int y)

{

    x=find(fa,x); y=find(fa,y);

    if (x==y)return 0;

    fa[y]=x;

    return 1;

}

void work()

{

    static int bl[N],d[N];

    queue<int>Q;

    int k=0,pd=0; tot=0;

    read(n); read(m);

    for(int i=1;i<=n;i++)bl[i]=i;

    memset(last,0,sizeof(int)*(n+1));

    memset(d,0,sizeof(int)*(n+1));

    for(int i=1;i<=m;i++)

        {

            int x,y; char id;

            read(x); read_char(id); read(y);

            x++; y++;

            if (id=='=')merge(bl,x,y);

            if (id=='>')edges[++k]={x,y};

            if (id=='<')edges[++k]={y,x};

        }

    for(int i=1;i<=n;i++)find(bl,i);

    for(int i=1;i<=k;i++)AddEdge(bl[edges[i].x],bl[edges[i].y]);

    for(int i=1;i<=tot;i++)d[edges[i].y]++;

    for(int i=1;i<=n;i++)if (bl[i]==i&&!d[i])Q.push(i);

    while(!Q.empty())

        {

            if (Q.size()>1)pd=2;

            int u=Q.front();Q.pop();

            d[u]=-1;

            for(int i=last[u];i;i=edges[i].s)

                {

                    Edge &e=edges[i];

                    d[e.y]--;

                    if (!d[e.y])Q.push(e.y);

                }

        }

    for(int i=1;i<=n;i++)if (bl[i]==i&&d[i]!=-1)pd=1;

    if (pd==1)printf("CONFLICT\n");

    else if (pd==0)printf("OK\n");

    else printf("UNCERTAIN\n");

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("aa.in","r",stdin);

#endif

    while(1)work();

}

巴特西

HDU 1811 并查集＋拓扑排序