Rank of Tetris (hdu 1811 拓撲排序)

Rank of Tetris

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

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

OK
CONFLICT
UNCERTAIN

        

//思路：先說建圖，“>”和“<”的情況相信大家都知道怎麼做，大的向小的連條邊就行，關鍵是“=”怎麼處理，做法是把等于的兩個人看成一個人，因為這兩個人的排名是可以比較的，是以隻要比較他們和其他人的排名順序就可以了，那麼就可以把他們看成一個人，比如說 1=2 ， 2=3 那麼就可以把2、3都看成是 1 ，這裡是用并查集實作（用一個root[]數組就好了）。

然後我們怎麼判斷是 UNCERTAIN還是CONFLICT還是OK：首先CONFLICT很好判斷，隻要拓撲排序不能把整張圖所有點都周遊完（即存在環）就是CONFLICT。UNCERTAIN呢？隻要拓撲排序的隊列裡一次進了2個及以上的點就一定是UNCERTAIN，舉個簡單的例子：1->2 , 1->3 ，顯然2、3的排名順序無法比較，1出隊列後，2，3進隊列，是以是UNCERTAIN。可以自己舉幾個例子驗證下。注意，如果同時UNCERTAIN和CONFLICT，輸出CONFLICT。如果兩者都不存在，就是OK。

拓撲排序這裡不介紹了。

findroot（）這個函數是用來找那個人的根的（因為存在“=”，有幾個人是看成一個人的）。是以先要把所有“=”的情況先處理完再去處理其他的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 10000 + 100;

int n, m;
int sum;
vector<int>map[MAX];
int indegree[MAX];
int root[MAX];

int findroot(int x)
{
	if (root[x] == x)
		return x;
	else
		return root[x] = findroot(root[x]);
}

int unionset(int a, int b)
{
	a = findroot(a);
	b = findroot(b);
	if (a == b)
		return 0;
	root[b] = a;
	return 1;
}

void init()
{
	for (int i = 0; i < n; i++)
	{
		map[i].clear();
		root[i] = i;
		indegree[i] = 0;
	}
}

void toposort()
{
	int cnt = 0;
	bool uncertain = false;
	queue<int>q;
	for (int i = 0; i < n; i++)
	{
		if (indegree[i] == 0 && findroot(i) == i)
			q.push(i);
	}
	while (!q.empty())
	{
		if (q.size() > 1)
			uncertain = true;
		int v = q.front();
		q.pop();
		for (int i = 0; i < map[v].size(); i++)
		{
			int u = map[v][i];
			indegree[u]--;
			if (!indegree[u])
				q.push(u);
		}
		cnt++;
	}
	if (cnt < sum)
		printf("CONFLICT\n");
	else if (uncertain)
		printf("UNCERTAIN\n");
	else
		printf("OK\n");
}

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		int a[MAX*2], b[MAX*2];
		char str[MAX*2];
		int x, y;
		sum = n;
		init();
		for (int i = 0; i < m; i++)
		{
			scanf("%d %c %d", &a[i], &str[i], &b[i]);
			if (str[i] == '=')
			{
				if (unionset(a[i], b[i]))
					sum--;
			}
		}
		for (int i = 0; i < m; i++)
		{
			x = findroot(a[i]);
			y = findroot(b[i]);
			if (str[i] == '>')
			{
				map[x].push_back(y);
				indegree[y]++;
			}
			else if (str[i] == '<')
			{
				map[y].push_back(x);
				indegree[x]++;
			}
		}
		toposort();
	}
	return 0;
}