Rank of Tetris
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9267 Accepted Submission(s): 2668
为了更好的符合那些爱好者的喜好，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"。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系
题目链接：HDU 1811
题意：给定N个点和M个关系，可以使=、>或<的关系，求能否唯一确定这N个点的大小关系。
看到等于号=可以用并查集来处理把相等关系的点都缩一个点，然后就是判断这个缩点之后的图是否是一个DAG，若不是DAG则说明是CONFLICT，否则再判断是否是UNCERTAIN，如何判断呢？用一个dis数组记录拓扑排序出的点距离起始点的层次关系，若存在两个缩点的dis相同，则说明这两个点关系不明确，或者存在某一个缩点它没有出边和入边，且它的秩小于总点数N，说明这个集合被孤立出去，集合内的点关系也是不明确的。当然一开始得先离线处理缩点，不然万一输入次序一变化，加的边就不对了
给两组数据：
3 1
1 = 0
UNCERTAIN
2 1
1 = 0
OK
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 10010;
const int M = 20010;
struct edge
{
int to, nxt;
edge() {}
edge(int _to, int _nxt): to(_to), nxt(_nxt) {}
} E[N];
struct info
{
int a, b;
char ops[3];
} rela[M]; int head[N], tot;
int in[N], out[N], pre[N], ran[N], cnt[N], vis[N], dis[N]; void init()
{
CLR(head, -1);
tot = 0;
CLR(in, 0);
CLR(out, 0);
CLR(pre, -1);
CLR(cnt, 0);
CLR(vis, 0);
CLR(dis, 0);
fill(ran, ran + N, 1);
}
int Find(int n)
{
return pre[n] == -1 ? n : pre[n] = Find(pre[n]);
}
void joint(int a, int b)
{
a = Find(a);
b = Find(b);
if (a == b)
return ;
pre[a] = b;
ran[b] += ran[a];
ran[a] = 0;
}
inline void add(int s, int t)
{
E[tot] = edge(t, head[s]);
head[s] = tot++;
}
int Top_sort1(int n)
{
queue<int>Q;
int i;
bool uncertain = false, conflict = false;
for (i = 0; i < n; ++i)
{
int fi = Find(i);
if (!vis[fi] && !in[fi])
{
Q.push(fi);
dis[fi] = 1;
++cnt[dis[fi]];
vis[fi] = 1;
}
if (!out[fi] && !in[fi] && ran[fi] < n)
uncertain = true;
}
CLR(vis, 0);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (--in[v] == 0)
{
Q.push(v);
dis[v] = dis[u] + 1;
if (!vis[v])
++cnt[dis[v]];
}
}
}
for (i = 0; i < n; ++i)
{
int fi = Find(i);
if (in[fi])
{
conflict = true;
break;
}
}
for (i = 1; i <= n; ++i)
{
if (cnt[i] >= 2)
{
uncertain = true;
break;
}
}
if (conflict)
return -1;
else if (uncertain)
return 0;
return 1;
}
int main(void)
{
int n, m, i;
while (~scanf("%d%d", &n, &m))
{
init();
for (i = 0; i < m; ++i)
{
scanf("%d %s %d", &rela[i].a, rela[i].ops, &rela[i].b);
if (rela[i].ops[0] == '=')
joint(rela[i].a, rela[i].b);
}
for (i = 0; i < m; ++i)
{
if (rela[i].ops[0] == '=')
continue;
if (rela[i].ops[0] == '<')
swap(rela[i].a, rela[i].b);
int fa = Find(rela[i].a), fb = Find(rela[i].b);
add(fa, fb);
++in[fb];
++out[fa];
}
int ans = Top_sort1(n);
if (ans == 1)
puts("OK");
else if (ans == 0)
puts("UNCERTAIN");
else
puts("CONFLICT");
}
return 0;
}