题目链接:传送门

题目大意:有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 ;
}

最新文章

  1. web 前端常用组件【02】Select 下拉框
  2. iOS 基础复习
  3. 黑马程序员——JAVA基础之多线程的安全问题
  4. noip2014普及组 比例简化
  5. python def说明
  6. Eclipse SVN插件安装与使用(2014.12.27——by小赞)
  7. HDOJ 3466 Proud Merchants
  8. 两个示例介绍JavaScript的闭包
  9. 51cto那些技术专题们
  10. Flex整合Spring
  11. 输入和输出--javase中的路径
  12. JavaScript(第十六天)【BOM基础】
  13. Python----简单线性回归
  14. Maven下Spring + SpringMvc + Hibernate4 配置实例
  15. linux通过命令行查看MySQL编码并修改-简洁版方法
  16. http之理解304
  17. pygame 笔记-6 碰撞检测
  18. JS浏览器Session存取数据
  19. Oracle Client 10g (instantclient) 精简版安装
  20. js中__proto__和prototype的区别和关系

热门文章

  1. Sql中存在斜杠“/”怎么办?
  2. 【DP】【单调队列】【NOI2005】瑰丽华尔兹
  3. scrollBy 相对滚动
  4. Cocos2dx 3.6源代码编译错误:syntax error : missing &amp;#39;)&amp;#39; before &amp;#39;{&amp;#39;
  5. 9、Linux驱动的杂项设备
  6. Atitit。Tree文件解析器的原理流程与设计实现&#160;&#160;java&#160;&#160;c#&#160;php&#160;js
  7. nginx正则说明
  8. java - day05 - Array
  9. fzu 2250 不可能弹幕结界 分析+模拟,考察思维严谨。
  10. 着手打造你的随身系统---将linux装进移动硬盘