首页 > 代码库 > （拓扑排序+并查集）HDU - 1811 Rank of Tetris
（拓扑排序+并查集）HDU - 1811 Rank of Tetris
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1811
题意：有个很多关系，现在需要产生一个名单，有的人比有的人牛逼，有的人没有的人牛逼，有的人一样牛逼，现在需要通过牛逼程度排名，如果1比2牛逼，1的排名就比2前，如果1和2一样牛逼，就比两个人的人品，人品好的人排前面。
现在有三种情况:
1、正确
2、矛盾
3、无法确定
分析：
这里其他方面还是比较简单。首先确定三种情况的发生条件：
矛盾--存在环，也就是在toposort之后，没有把所有的点全都访问到。
无法确定--只要存在一次入度为0的点不止一个，那么这个拓扑序就不唯一，所以无法确定。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <queue> 8 #include <cstring> 9 #include <algorithm> 10 11 using namespace std; 12 13 14 typedef long long ll; 15 typedef unsigned long long ull; 16 #define inf (0x3f3f3f3f) 17 #define lnf (0x3f3f3f3f3f3f3f3f) 18 #define eps (1e-8) 19 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1 ;} 20 21 //------------------------------------------------- 22 23 24 const int maxn=10010; 25 vector<int> edge[maxn]; 26 27 int indu[maxn]; 28 int par[maxn]; 29 int ranks[maxn]; 30 int u[maxn],v[maxn]; 31 int n,m; 32 int rn; 33 char op[maxn][3]; 34 35 void init(){ 36 for(int i=0;i<n;i++){ 37 par[i]=i; 38 ranks[i]=0; 39 edge[i].clear(); 40 } 41 memset(indu,0,sizeof(indu)); 42 } 43 44 int findx(int x){ 45 if(par[x]==x)return x; 46 else return par[x]=findx(par[x]); 47 } 48 49 bool unite(int x,int y){ 50 x=findx(x); 51 y=findx(y); 52 if(x==y)return false; 53 if(ranks[x]>ranks[y]){ 54 par[y]=x; 55 } 56 else{ 57 if(ranks[x]==ranks[y]){ 58 ranks[y]++; 59 } 60 par[x]=y; 61 } 62 return true; 63 } 64 65 66 bool toposort(){ 67 queue<int> q; 68 for(int i=0;i<n;i++){ 69 if(indu[i]==0&&i==findx(i)){ 70 indu[i]--; 71 q.push(i); 72 } 73 } 74 bool allon=false; 75 76 while(!q.empty()){ 77 if(q.size()>1)allon=true; 78 int u=q.front(); 79 q.pop(); 80 rn--; 81 for(int i=0;i<edge[u].size();i++){ 82 indu[edge[u][i]]--; 83 if(indu[edge[u][i]]==0){ 84 q.push(edge[u][i]); 85 } 86 } 87 } 88 return allon; 89 } 90 91 92 void solve(){ 93 while(~scanf("%d%d",&n,&m)){ 94 init(); 95 rn=n; 96 for(int i=0;i<m;i++){ 97 scanf("%d%s%d",&u[i],op[i],&v[i]); 98 if(op[i][0]==‘=‘){ 99 if(unite(u[i],v[i])){100 rn--;101 }102 }103 }104 for(int i=0;i<m;i++){105 if(op[i][0]!=‘=‘){106 int x=findx(u[i]);107 int y=findx(v[i]);108 if(op[i][0]==‘>‘){109 edge[x].push_back(y);110 indu[y]++;111 }112 else{113 edge[y].push_back(x);114 indu[x]++;115 }116 }117 }118 bool allon=toposort();119 if(rn>0){120 puts("CONFLICT");121 } 122 else if(allon){123 puts("UNCERTAIN");124 }125 else{126 puts("OK");127 }128 }129 130 }131 132 133 134 int main(){135 136 #ifndef ONLINE_JUDGE137 freopen("1.in","r",stdin);138 //freopen("1.out","w",stdout);139 #endif140 141 solve();142 }
（拓扑排序+并查集）HDU - 1811 Rank of Tetris
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。