A Bug's Life HDU - 1829 种类并查集
2024-10-08 08:46:52
//有n个成员,并查集开两倍空间
//1~n为一组, n+1~2n为一组。a与b互斥,则a与b反(即b+n)为同一集合,
//同时b与a反(a+n)为同一集合 //在union操作中,引入w ,w越大,表面它的根连接的点越多
//合并时确立关系
#include<iostream>
using namespace std;
const int N=1e6;
int p[N];
int w[N];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
void unite(int x, int y)
{
int px=find(x),py=find(y);
if (px==py)
return;
else if(w[px]>w[py])
p[py] = px;
else
{
p[px]=py;
if (w[px]==w[py])
w[py]+=w[px];
}
}
bool judge(int x,int y)
{
int px=find(x);
int py=find(y);
return px==py;
}
int main()
{
int t;
cin>>t;
int cnt=;
int n,m;
while(t--)
{
bool flag=;
cin>>n>>m;
for(int i=;i<=*n;i++)
p[i]=i,w[i]=;
int a,b;
for(int i=;i<m;i++)
{
cin>>a>>b;
if (judge(a,b)||judge(a,b+n))
{
if (judge(a,b))
flag=false;
//是异性则符合条件继续
else
continue;
}
else
{
unite(a, b+n);
unite(a+n, b);
}
}
printf("Scenario #%d:\n",++cnt);
if(!flag)
printf("Suspicious bugs found!\n\n");
else
printf("No suspicious bugs found!\n\n");
}
}
最新文章
- ASP.NET MVC 从零开始 - 请求处理
- lnmp的使用
- 联想电脑win7旗舰版环境下的如何成功配置AppServ
- Android 音乐播放器之--错误状态下调用导致的异常
- Stm32 SWD 下载 调试配置
- [React] React Router: Querystring Parameters
- http Post 请求一网络资源返回字符串
- OpenWrt配置opkg.conf
- OPENCV条形码检测与识别
- 【MySQL】存储emoji表情报错(Incorrect string value: &#39;\xF0\x9F\x98\x82\xF0\x9F...&#39;)的解决方案
- 版本视图找不到数据 EDITIONING VIEW
- j2ee高级开发技术课程第五周
- share a story on OSPF &; BGP
- 查看mobileprovision信息
- 洛谷 3706 [SDOI2017]硬币游戏——思路
- C#日期格式化英文月份 VS改大小写的快捷键
- vuejs模仿实现一个电影分享类网站
- 计算机基础和Linux基础
- Yii2基础常用笔记
- 处理iOS设备的屏幕旋转
热门文章
- ls-remote -h -t git://github.com/adobe-webplatform/eve.git
- C#开源组件DocX处理Word文档基本操作(一)
- iptables 实例
- JVM源码分析之临门一脚的OutOfMemoryError完全解读
- QT学习之路-QT服务器-mysql数据库相关问题集锦(1)
- android button的selector
- C——简单计算器(HDU1237)
- 【转】netty-transport版本冲突
- 普通版js运动框架
- [MongoDB] 使用PHP根据_id字段查询数据