首页 / 算法 / hdu 1811(拓扑排序+并查集)
hdu 1811(拓扑排序+并查集)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hdu 1811(拓扑排序+并查集),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2769字,纯文字阅读大概需要4分钟。
内容图文
![hdu 1811(拓扑排序+并查集)](/upload/InfoBanner/zyjiaocheng/1269/ae8aa82ddf59498490bc658c446a120c.jpg)
Rank of Tetris
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7961 Accepted Submission(s): 2266
为 了更好的符合那些爱好者的喜好,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"。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行,分别表示这些关系
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> usingnamespace std; constint N =10005; int n,m; int father[N]; int indegree[N]; struct Node{ int a,b; char s; }node[2*N]; struct Edge{ int u,v,next; }edge[2*N]; int head[N]; int _find(int x){ if(x!=father[x]) father[x] = _find(father[x]); return father[x]; } void Union(int a,int b){ int x = _find(a); int y = _find(b); if(x==y) return ; father[x] = y; } void addedge(int u,int v,int &k){ edge[k].u = u,edge[k].v = v; edge[k].next = head[u],head[u]=k++; } int main() { while(scanf("%d%d",&n,&m)!=EOF){ for(int i=0;i<n;i++) { father[i] = i; head[i] = -1; indegree[i] = 0; } bool flag = true,flag1 = true; ///flag判断冲突,flag1判断完整性int cnt = n; for(int i=0;i<m;i++){ scanf("%d %c %d",&node[i].a,&node[i].s,&node[i].b); if(node[i].s==‘=‘){ Union(node[i].a,node[i].b); cnt--; } } int tot = 0; for(int i=0;i<m;i++){ char s = node[i].s; int a = node[i].a,b = node[i].b; int x = _find(a); int y = _find(b); if(s!=‘=‘&&x==y) flag = false; if(s==‘<‘){ indegree[x]++; addedge(y,x,tot); } if(s==‘>‘){ indegree[y]++; addedge(x,y,tot); } } queue<int> q; for(int i=0;i<n;i++){ if(indegree[i]==0&&father[i]==i){ q.push(i); } } while(!q.empty()){ int t = q.front(); q.pop(); cnt--; if(!q.empty()) flag1 = false; ///存在多个入度为0的点,答案不唯一for(int k = head[t];k!=-1;k=edge[k].next){ int v = edge[k].v; indegree[v]--; if(indegree[v]==0) q.push(v); } } if(cnt>0) flag = false; if(!flag) printf("CONFLICT\n"); elseif(!flag1) printf("UNCERTAIN\n"); else printf("OK\n"); } return0; }
原文:http://www.cnblogs.com/liyinggang/p/5486241.html
内容总结
以上是互联网集市为您收集整理的hdu 1811(拓扑排序+并查集)全部内容,希望文章能够帮你解决hdu 1811(拓扑排序+并查集)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。