Rank of Tetris HDU--1881

Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4031 Accepted Submission(s): 1133

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

CONFLICT

UNCERTAIN

思路：

此题花了我好长时间，一开始以为rating相同的点就直接比较rp然后建图，后来想想不对，因为这样发现不了冲突。后来一想对于rating相同的点可以不用排序，因为对于这些点，他们的rp必然不相同，也就是说在这些点的内部必然存在唯一的且合理的排序，因此只需将要将这些点合并成一个点即可，需要用到并查集的知识。

把所有点按上述方法处理后就会得到一些点（暂且称为“有效点”），对于这些有效点再进行拓扑排序即可。

冲突情形：到最后存在环，或者出现a > b,b > c 且 c >a；

不确定情形：同一层中不止一个点入度为0；

确定情形：除以上两种情形;

AC代码:

  1 #include<stdio.h>
  2 #include<string.h>
  3 typedef struct
  4 {
  5     int to;
  6     int next;
  7 }EdgeNode;
  8 int cnt;
  9 char str[6];
 10 EdgeNode Edge[20005];
 11 int father[10005],depth[10005];
 12 int L[10005],M[10005],R[10005];
 13 int head[10005],indegree[10005];
 14 int vis[10005],node[10005],temp[10005];
 15 void init(int n)
 16 {
 17     int i;
 18     cnt = 0;
 19     memset(vis,0,sizeof(vis));
 20     memset(head,-1,sizeof(head));
 21     memset(indegree,0,sizeof(indegree));
 22     for(i = 0;i < n;i ++)
 23     {
 24         father[i] = i;
 25         depth[i] = 0;
 26     }
 27 }
 28 
 29 int find(int x)
 30 {
 31     if(x == father[x])
 32         return x;
 33     return father[x] = find(father[x]);
 34 }
 35 
 36 void uint(int x,int y)
 37 {
 38     x = find(x);
 39     y = find(y);
 40     if(x == y)
 41         return ;
 42     if(depth[x] < depth[y])
 43         father[x] = y;
 44     else
 45     {
 46         if(depth[x] > depth[y])
 47             father[y] = x;
 48         else
 49         {
 50             father[x] = y;
 51             depth[y]++;
 52         }
 53     }
 54     return ;
 55 }
 56 
 57 void add_edge(int n,int m)
 58 {
 59     Edge[cnt].to = m;
 60     Edge[cnt].next = head[n];
 61     head[n] = cnt++;
 62 }
 63 
 64 int main(void)
 65 {
 66     int a,b,n,m,i,j,k;
 67     int sum,flag_U,flag_C;
 68     while(~scanf("%d %d",&n,&m))
 69     {
 70         init(n);
 71         flag_U = flag_C = 0;
 72         for(i = 1;i <= m;i ++)
 73         {
 74             scanf("%d %c %d",&L[i],&M[i],&R[i]);
 75             if(M[i] == '=')
 76             {
 77                 uint(L[i],R[i]);
 78             }
 79         }
 80         for(i = 1;i <= m;i ++)
 81         {
 82             if(M[i] == '=')
 83                 continue ;
 84             a = find(L[i]);
 85             b = find(R[i]);
 86             if(a == b)
 87             {
 88                 flag_C = 1;
 89                 break ;
 90             }
 91             else
 92             {
 93                 if(M[i] == '>')
 94                 {
 95                     add_edge(b+1,a+1);
 96                     indegree[a+1]++;
 97                 }
 98                 else
 99                 {
100                     add_edge(a+1,b+1);
101                     indegree[b+1]++;
102                 }
103             }
104         }
105         for(i = 1;i <= n;i ++)
106         {
107             sum = 0;
108             for(j = 1;j <= n;j ++)
109             {
110                 if(indegree[j] == 0 && vis[j] == 0 && father[j-1] == j-1)
111                     temp[sum++] = j;
112             }
113             if(sum > 1)
114                 flag_U = 1;
115             for(j = 0;j < sum;j ++)
116             {
117                 vis[temp[j]] = 1;
118                 for(k = head[temp[j]];k != -1;k = Edge[k].next)
119                 {
120                     if(!vis[Edge[k].to])
121                         indegree[Edge[k].to]--;
122                 }
123             }
124         }
125         for(i = 1;i <= n;i ++)
126         {
127             if(indegree[i] && father[i-1] == i-1)
128             {
129                 flag_C = 1;
130                 break ;
131             }
132         }
133         if(!(flag_C+flag_U))
134             printf("OK
");
135         if(flag_C)
136             printf("CONFLICT
");
137         if(flag_U && !flag_C)
138             printf("UNCERTAIN
");
139     }
140     return 0;
141 }