博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU1829【种类并查集】
阅读量:5116 次
发布时间:2019-06-13

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

题意:
检验给出条件是否有同性恋。
思路:
条件并查集。
还是一个类似的前缀和,sum[x]是x到根这段路径上的和,根一定是坐标越小的,
那么如果说对于同类(同一个集合)的判断就sum[a]是否等于sum[b]
对于不同类的话,就是他们的关系取反。

考虑状态压缩中,关系就是叠加。

一直wa,wa在Find以后是判断各自的关系。

#include
using namespace std;const int N=2e3+10;int pre[N],n,sum[N],m;bool flag;int Find(int x){ if(pre[x]==x) return x; int temp=pre[x]; pre[x]=Find(temp); sum[x]=(sum[x]+sum[temp])%2; return pre[x];}void Merge(int x,int y){ int xx=Find(x); int yy=Find(y); if(xx==yy) { if(sum[x]==sum[y]) flag=false; } else{ pre[xx]=yy; sum[xx]=(sum[y]+sum[x]+1)%2; //父子之间不是同性恋; }}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) { pre[i]=i; sum[i]=0; } flag=true; while(m--) { int x,y; scanf("%d%d",&x,&y); if(!flag) continue; Merge(x,y); } printf("Scenario #%d:\n",cas++); if(flag) puts("No suspicious bugs found!"); else puts("Suspicious bugs found!"); puts(""); } return 0;}

转载于:https://www.cnblogs.com/keyboarder-zsq/p/6777445.html

你可能感兴趣的文章
Java语言概述
查看>>
关于BOM知识的整理
查看>>
使用word发布博客
查看>>
面向对象的小demo
查看>>
微服务之初了解(一)
查看>>
GDOI DAY1游记
查看>>
MyBaits动态sql语句
查看>>
HDU4405(期望DP)
查看>>
拉格朗日乘子法 那些年学过的高数
查看>>
vs code 的便捷使用
查看>>
Spring MVC @ResponseBody返回中文字符串乱码问题
查看>>
用户空间与内核空间,进程上下文与中断上下文[总结]
查看>>
JS 中的跨域请求
查看>>
JAVA开发环境搭建
查看>>
mysql基础语句
查看>>
Oracle中的rownum不能使用大于>的问题
查看>>
cassandra vs mongo (1)存储引擎
查看>>
Visual Studio基于CMake配置opencv1.0.0、opencv2.2
查看>>
遍历Map对象
查看>>
MySQL索引背后的数据结构及算法原理
查看>>