hdu1829(A Bug's Life)
2024-09-28 14:08:35
题目链接:传送门
题目大意:有n个昆虫,有m组关系,接下来m行表示两个昆虫性别不同,问是否有矛盾情况(同男同女)
题目思路:并查集的高级应用,开两倍数组大小,后n个数组表示和当前昆虫不同性别的集合
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define seg int root,int l,int r
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 100000007
#define inf 0x3f3f3f3f
#define N 100005
#define maxn 10001000
typedef long long LL;
typedef pair<int,int> PII; int fp[N];
int findp(int x){return fp[x]==x?x:fp[x]=findp(fp[x]);} int main(){
int i,j,group,k,v,x,y,Case=,n,m;
scanf("%d",&group);
while(group--){
int flag=;
scanf("%d%d",&n,&m);
for(i=;i<=n<<;++i) fp[i]=i;
for(i=;i<m;++i){
scanf("%d%d",&x,&y);
if(!flag){
int xa=findp(x);
int ya=findp(y);
if(xa==ya) flag=;
else{
fp[xa]=findp(y+n);
fp[ya]=findp(x+n);
}
}
}
printf("Scenario #%d:\n",++Case);
if(flag) printf("Suspicious bugs found!\n\n");
else printf("No suspicious bugs found!\n\n");
}
return ;
}
最新文章
- web 前端常用组件【02】Select 下拉框
- iOS 基础复习
- 黑马程序员——JAVA基础之多线程的安全问题
- noip2014普及组 比例简化
- python def说明
- Eclipse SVN插件安装与使用(2014.12.27——by小赞)
- HDOJ 3466 Proud Merchants
- 两个示例介绍JavaScript的闭包
- 51cto那些技术专题们
- Flex整合Spring
- 输入和输出--javase中的路径
- JavaScript(第十六天)【BOM基础】
- Python----简单线性回归
- Maven下Spring + SpringMvc + Hibernate4 配置实例
- linux通过命令行查看MySQL编码并修改-简洁版方法
- http之理解304
- pygame 笔记-6 碰撞检测
- JS浏览器Session存取数据
- Oracle Client 10g (instantclient) 精简版安装
- js中__proto__和prototype的区别和关系
热门文章
- Sql中存在斜杠“/”怎么办?
- 【DP】【单调队列】【NOI2005】瑰丽华尔兹
- scrollBy 相对滚动
- Cocos2dx 3.6源代码编译错误:syntax error : missing &;#39;)&;#39; before &;#39;{&;#39;
- 9、Linux驱动的杂项设备
- Atitit。Tree文件解析器的原理流程与设计实现&#160;&#160;java&#160;&#160;c#&#160;php&#160;js
- nginx正则说明
- java - day05 - Array
- fzu 2250 不可能弹幕结界 分析+模拟,考察思维严谨。
- 着手打造你的随身系统---将linux装进移动硬盘