POJ - 2492 种类并查集
2024-10-18 22:38:15
思路:保存每个点与其父节点的关系,注意合并和路径压缩即可。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 2000 + 5; struct node{ int par; int real; //0表示同性,1表示性别相异 }a[maxn]; int find(int x, int &root) { if(a[x].par == x) { root = x; return a[x].real; } int r = (a[x].real + find(a[x].par, root)) % 2; a[x].par = root; return a[x].real = r; } bool unionset(int x, int y) { int r1, r2; int rx = find(x, r1), ry = find(y, r2); if(r1 == r2) { if(rx == ry) return false; } else { a[r1].par = y; a[r1].real = (rx + 1) % 2; } return true; } int main() { int n, m, T, kase = 1; scanf("%d", &T); while(T--) { if(kase > 1) printf("\n"); scanf("%d%d", &n, &m); for(int i = 0; i <= n; ++i) { a[i].par = i; a[i].real = 0; } int x, y; int flag = 1; for(int i = 0; i < m; ++i) { scanf("%d%d", &x, &y); if(flag && !unionset(x, y)) { flag = 0; } } printf("Scenario #%d:\n", kase++); if(flag) printf("No suspicious bugs found!\n"); else printf("Suspicious bugs found!\n"); } return 0; }
如有不当之处欢迎指出!
最新文章
- linux驱动之USB驱动程序
- CentOS下 pycharm开发环境搭建之无穷无尽的问题
- UVa 1347 Tour
- 用UIImageView作出动画效果
- XMLParser解析xml--内容源自网络(在静态库中不能用GDATA来解析,因为静态库不能加动态库)
- Get ListView items from other windows z
- NPOI控件的使用导出excel文件和word文件
- IP地址段遍历
- python---购物车---更新
- Elasticsearch通关教程(五):如何通过SQL查询Elasticsearch
- codecademy quiz——JavaScript Promise
- python 获取当前文件夹下所有文件名
- 自己动手实现RPC
- JMD Handy Baby 2 to Decode &; Adding New BMW 525 ID46 Key
- webpack4+node合并资源请求, 实现combo功能(二十三)
- PAT A1120 Friend Numbers (20 分)——set
- Linux dnsmasq.conf
- Hadoop2.6.5集群搭建
- 用yum下载rpm包(不安装)到制定目录
- POJ 2975 Nim(博弈)题解
热门文章
- Log4j源码解析--Appender接口解析
- 无废话XML--DOM4J
- 【javaweb学习笔记】WEB01_HTML
- 错误: 非法字符: &#39;\ufeff&#39;
- android activity传递实体类对象
- thinkphp5踩坑之部署到服务器模板不存在
- ansible基础及使用示例
- BZOJ 1076: [SCOI2008]奖励关 [DP 期望 状压]
- BZOJ 3963: [WF2011]MachineWorks [CDQ分治 斜率优化DP]
- rsync实现数据增量备份