hdu 1811 Rank of Tetris(并查集+拓撲排序)

自從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      

思路：

本題關鍵在于對出現的“=”進行處理，用到并查集，将兩個點連在一起。在拓撲排序時，如果出現環，那麼肯定有元素不能參與排序，此時判定為沖突。如果有兩個元素同時加入了隊列，那就說明拓撲排序不唯一，此時判斷為資訊不完全。

注意：若資訊沖突且不完全，判定為資訊沖突。當兩個點加入并查集之後，元素總數要減一。處理完“=”之後才可以建立鄰接表，不然會導緻排序不連續。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int mx = 2e4 + 5;
int head[mx], in[mx], fa[mx], tol, cnt;
int a[mx],b[mx];
int n, m;
char ch[mx];

struct a{
	int to, next;
}edge[mx];

void add(int u, int v){
	edge[tol].to = v;
	edge[tol].next = head[u];
	head[u]= tol++; 
}
int find(int x){
	if(x != fa[x])
		fa[x] = find(fa[x]);
	return fa[x];
}
void topu(){
	queue<int>q;
	while(!q.empty()) q.pop();
	
	for(int i = 0; i < n; i++){
		if(i == find(i) && in[i] == 0)
			q.push(i); 
	}
	int flag = 0, co = 0,u;
	while(!q.empty()){
		if(q.size() > 1) flag = 1;
		u = q.front();
		q.pop();
		cnt--;
		for(int i = head[u]; i != -1; i = edge[i].next){
			if(--in[edge[i].to] == 0) q.push(edge[i].to);
		}
	}
	if(cnt) {
		puts("CONFLICT");
		return;
	}
	if(flag){
		puts("UNCERTAIN");
		return;	
	}
	puts("OK");
}

void init(){
	memset(head, -1, sizeof(head));
	memset(in, 0, sizeof(in));
	for(int i = 0; i < mx; i++)
		fa[i] = i;
	tol = 0;
	cnt = n;
}


int main(){
	while(scanf("%d%d", &n, &m) != EOF){
		init();
	
		for(int p=0;p<m;p++)
               {
                       scanf("%d %c %d", &a[p], &ch[p], &b[p]);
                       if(ch[p]=='=')
                       {
                              int i=find(a[p]);
                               int j=find(b[p]);
                               if(i!=j)fa[i]=j,cnt--;
                       }
               }
               for(int p=0;p<m;p++)
               {
                       if(ch[p]=='=')continue;
                      if(ch[p]=='>')
                      {
                            int i=find(a[p]);
                            int j=find(b[p]);
                            add(i,j);
                            in[j]++;
                      }
                      else if(ch[p]=='<')
                      {
                            int i=find(a[p]);
                            int j=find(b[p]);
                            add(j,i);
                            in[i]++;
                      }
                }
		topu();
	
	}

	return 0;
}