Rank of TetrisTime Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5672Accepted Submission(s): 1616
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 30 > 11 < 20 > 24 41 = 21 > 32 > 00 > 13 31 > 01 > 22 < 1
Sample Output
OKCONFLICTUNCERTAIN
有时候感觉自己真笨。
上一个人的博客吧。
代码：#include <cstdio>#include <queue>#include <cstring>#define MAX 10100using namespace std ;struct Node{int to,next;}edge[2*MAX];int f[MAX] , head[MAX] ,a[2*MAX],b[2*MAX] , in[MAX];char ch[2*MAX] ;bool visited[MAX] ;void init(int n){for(int i = 0 ; i <= n ; ++i){f[i] = i ;head[i] = -1 ; visited[i] = false ;in[i]=0;}}int find(int x){int r=x ;while(r != f[r]){r = f[r] ;}int temp = x ;while(temp != r){x = f[temp] ;f[temp] = r ;temp = x ;}return r ;}int main(){int m , n;while(scanf("%d%d",&n,&m) != EOF){init(n) ;int num = n ;for(int i = 0 ; i < m ; ++i){scanf("%d %c %d",a+i,ch+i,b+i) ;if(ch[i] == '='){int fa = find(a[i]),fb = find(b[i]) ;if(fa != fb){f[fa] = f[fb] ;num– ;}}}int index = 0 ;bool flag = false ;for(int i = 0 ; i < m ; ++i){if(ch[i] == '=')continue ;int fa = find(a[i]) , fb = find(b[i]) ;//一定要注意这个，每次都是直接更新到父结点上！！if(fa == fb){flag = true ;break ;}if(ch[i] == '>'){bool repeat = false ;for(int j = head[fa] ; j != -1 ; j = edge[j].next)//防止重边，下同{if(edge[j].to == fb){repeat = true ;break ;}}if(!repeat){edge[index].to = fb;//不是更新当前的边，，而是从更新父结点。edge[index].next = head[fa] ;head[fa] = index++ ;in[fb] ++;}}else if(ch[i] == '<'){bool repeat = false ;for(int j = head[fb] ; j != -1 ; j = edge[j].next){if(edge[j].to == fa){repeat = true ;break ;}}if(!repeat){edge[index].to = fa;edge[index].next = head[fb];head[fb] = index ++ ;in[fa]++ ;}}}if(flag){puts("CONFLICT");continue ;}flag = false ;queue<int> que ;for(int i = 0 ; i < n ; ++i){if(in[i] == 0 && i == find(i)){que.push(i) ;}}while(!que.empty()){if(que.size()>1){flag = true ;}num– ;int j = que.front() ;que.pop() ;visited[j] = true ;for(int k = head[j] ; k != -1 ; k = edge[k].next){in[edge[k].to]–;if(!visited[edge[k].to] && in[edge[k].to]==0){que.push(edge[k].to) ;}}}if(num>0){puts("CONFLICT") ;}else if(flag){puts("UNCERTAIN") ;}else{puts("OK") ;}}return 0 ;}与君共勉
，努力爱一个人。付出，不一定会有收获；
