博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu1811 并查集+拓扑序
阅读量:7275 次
发布时间:2019-06-29

本文共 847 字,大约阅读时间需要 2 分钟。

题意:现在有一个排名系统,有一系列信息,分别是 > < = 的比较,而如果最终相等,就会将这些相等的按照序号从小到大排,问给出的信息是否可以确定完整的排序。

由于如果很多点相等,他们肯定能够确定名次,那么我们只要让他们共同拥有与其他点的大小关系就行了。所以就用到了并查集,将相等的点加入并查集,再对并查集排拓扑序,如果能够排出唯一的拓扑序,那么在每个并查集内部也能够有唯一的顺序。

1 #include
2 #include
3 #include
4 using namespace std; 5 const int maxn=1e4+5; 6 const int maxm=2e4+5; 7 8 int fa[maxn],num,n; 9 int a[maxm],b[maxm];10 char c[maxm][10];11 int head[maxn],point[maxm],nxt[maxm],size;12 int id[maxn];13 14 void init(){
for(int i=0;i
q;29 bool f=1;30 for(int i=0;i
'){75 add(find(a[i]),find(b[i]));76 }77 else if(c[i][0]=='<'){78 add(find(b[i]),find(a[i]));79 }80 }81 int tmp=topo();82 if(tmp==1)printf("OK\n");83 else if(tmp==0)printf("CONFLICT\n");84 else if(tmp==-1)printf("UNCERTAIN\n");85 }86 }
View Code

 

转载于:https://www.cnblogs.com/cenariusxz/p/4795127.html

你可能感兴趣的文章
30岁前不必在乎的30件事
查看>>
.NET 3.5(1) - VS 2008新特性之Multi Targeting(多定向)
查看>>
sql操作归类百分比
查看>>
POJ 2584 T-Shirt Gumbo (Dinic 或 SAP)
查看>>
如何证明Application Domain的隔离性
查看>>
[Leetcode] Reverse Nodes in k-Group
查看>>
【Swift学习】Swift编程之旅(二)
查看>>
OAuth 2.0协议在SAP产品中的应用
查看>>
树的重心
查看>>
快速搭建你的 github pages 个人博客 —— 基于 Create-React-App 的单页面应用实践...
查看>>
NPM酷库:winston 多路日志记录
查看>>
vue中的methods、computed和watch
查看>>
js 中的基本类型,引用类型,基本包装类型
查看>>
Word强大插件Writage使用手册
查看>>
CentOS7下PHP7.2安装redis扩展
查看>>
聊聊FilterSecurityInterceptor
查看>>
让数据库变快的10个建议
查看>>
Spring Boot 揭秘与实战
查看>>
【327天】跃迁之路——程序员高效学习方法论探索系列(实验阶段85-2017.12.29)...
查看>>
Redux 源码解析系列 -- Redux的实现思想
查看>>