POJ 2492 A Bug's Life 题解
2024-09-05 16:14:30
这道题是一道标准的种类并查集:
种类并查集是给每个结点一个权值。然后在合并和查找的时候根据情况对权值来进行维护。
通过将原有的区间范围变大使并查集可以维护种类的联系:
#include <iostream>
#include <cstdio>
using namespace std;
int f[];
int zhaobaba(int x)
{
if(f[x]==x) return x;
return f[x]=zhaobaba(f[x]);
}
int main()
{
int T;
cin>>T;
int t=T;
while(t--){
int n,m;
cin>>n>>m;
for(int i=;i<=*n;i++) f[i]=i;
bool lala=;
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(lala) continue;
if(zhaobaba(u)==zhaobaba(v)){
lala=;
continue;
}
f[zhaobaba(u)]=zhaobaba(v+n);
f[zhaobaba(u+n)]=zhaobaba(v);
}
cout<<"Scenario #"<<T-t<<":"<<endl;
if(!lala){
cout<<"No suspicious bugs found!"<<endl;
}
else{
cout<<"Suspicious bugs found!"<<endl;
}
cout<<endl;
}
}
最新文章
- Servlet、Filter、Listener、Interceptor
- HTML5+CSS3+Jquery实现纯手工的垂直时光轴【附源码】
- 《笨办法学C》笔记之指针
- Linux 命令执行结果输出到屏幕的同时写入到文件中
- MVC &ndash; 4.mvc初体验(1)
- ubuntu15.10 给解压版的eclipse安装桌面快捷方式
- js 操作select和option
- js中的垃圾回收机制
- javaScript动态参数
- 215. Kth Largest Element in an Array
- 2014第2周四部署环境&;买火车票
- 移动端-弹窗demo
- Java转型(向上转型和向下转型)
- 服务器大量的fin_wait1 状态长时间存在原因分析
- 第二周Python讲课内容--日记
- Android开发中Chronometer的用法
- Oracle 存储过程入门(一)
- 高可用集群(crmsh详解)http://www.it165.net/admin/html/201404/2869.html
- QT 登陆对话框
- linux支持的内存根文件系统