题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1811
题目概述：
中文题就略了。
大致思路：
显然这是一个拓扑排序的问题，不过题中有两个点rating相等的情况，我们发现因为不关心最后的排序结果，所以用并查集合并一下相等的点这时候就是求一个有向图的拓扑序了。
题中conflict的情况是图中有环，uncertain的情况是所求排序不唯一，此时只需要将有向图反向，再求一遍拓扑序对比一下之前求的拓扑序，如果有差异则说明情况为uncertain，否则为OK。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <vector> 6 #include <ctime> 7 #include <map> 8 #include <stack> 9 #include <queue> 10 #include <cstring> 11 #include <algorithm> 12 using namespace std; 13 14 #define sacnf scanf 15 #define scnaf scanf 16 #define maxn 10010 17 #define maxm 26 18 #define inf 1061109567 19 #define Eps 0.00001 20 const double PI=acos(-1.0); 21 #define mod 1000033 22 #define MAXNUM 10000 23 void Swap(int &a,int &b) {int t=a;a=b;b=t;} 24 int Abs(int x) {return (x<0)?-x:x;} 25 typedef long long ll; 26 typedef unsigned int uint; 27 28 struct node 29 { 30 int from,to; 31 char cmp; 32 } edge[maxn]; 33 34 vector<int> G[maxn]; 35 int in[maxn],ans[maxn],p[maxn],cnt,equals; 36 37 int found(int x) {return (p[x]==x)?x:p[x]=found(p[x]);} 38 39 void toposort(int n) 40 { 41 queue<int> q; 42 for(int i=0;i<n;i++) 43 if(i==p[i]&&!in[i]) q.push(i); 44 cnt=0; 45 while(!q.empty()) 46 { 47 int u=q.front();q.pop(); 48 ans[cnt++]=u; 49 int len=G[u].size(); 50 for(int i=0;i<len;i++) 51 { 52 int v=G[u][i]; 53 in[v]--; 54 if(!in[v]) q.push(v); 55 } 56 } 57 } 58 59 void re_toposort(int n) 60 { 61 if(cnt<n-equals) {printf("CONFLICT ");return;} 62 priority_queue<int,vector<int>,greater<int> > q; 63 for(int i=0;i<n;i++) 64 if(i==p[i]&&!in[i]) q.push(i); 65 while(!q.empty()) 66 { 67 int u=q.top();q.pop(); 68 if(ans[--cnt]!=u) {printf("UNCERTAIN ");return;} 69 int len=G[u].size(); 70 for(int i=0;i<len;i++) 71 { 72 int v=G[u][i]; 73 in[v]--; 74 if(!in[v]) q.push(v); 75 } 76 } 77 printf("OK "); 78 } 79 80 int main() 81 { 82 //freopen("data.in","r",stdin); 83 //freopen("flyer.out","w",stdout); 84 //clock_t st=clock(); 85 int n,m; 86 while(~scanf("%d%d",&n,&m)) 87 { 88 for(int i=0;i<n;i++) {G[i].clear();in[i]=0;p[i]=i;} 89 int a,c;char b;equals=0; 90 for(int i=1;i<=m;i++) 91 { 92 scanf("%d %c %d",&edge[i].from,&edge[i].cmp,&edge[i].to); 93 a=edge[i].from;b=edge[i].cmp;c=edge[i].to; 94 if(b=='=') 95 { 96 int x=found(a); 97 int y=found(c); 98 if(x!=y) {p[x]=y;equals++;} 99 } 100 } 101 for(int i=1;i<=m;i++) 102 { 103 a=edge[i].from;b=edge[i].cmp;c=edge[i].to; 104 a=found(a);c=found(c); 105 if(b=='<') {G[c].push_back(a);in[a]++;} 106 else if(b=='>') {G[a].push_back(c);in[c]++;} 107 } 108 /*for(int i=0;i<n;i++) 109 { 110 printf("%d :",i); 111 int len=G[i].size(); 112 for(int j=0;j<len;j++) 113 { 114 printf(" %d",G[i][j]); 115 } 116 printf(" %d ",in[i]); 117 }*/ 118 toposort(n); 119 for(int i=0;i<n;i++) {G[i].clear();in[i]=0;} 120 for(int i=1;i<=m;i++) 121 { 122 a=edge[i].from;b=edge[i].cmp;c=edge[i].to; 123 a=found(a);c=found(c); 124 if(b=='<') {G[a].push_back(c);in[c]++;} 125 else if(b=='>') {G[c].push_back(a);in[a]++;} 126 } 127 re_toposort(n); 128 } 129 //clock_t ed=clock(); 130 //printf(" Time Used : %.5lf Ms. ",(double)(ed-st)/CLOCKS_PER_SEC); 131 return 0; 132 }