Chenfan Blog

Do cool things that matter.

0%

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个点,然后进行后序的拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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\n");
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\n");
else if (flag) printf("UNCERTAIN\n");
else printf("OK\n");
}

return 0;
}