一、题面

POJ2492

二、分析

并查集判断类别的题目感觉套路都差不多。

还是先判断在不在一个集合里,在一个集合里才能判断是否同类。

若不在一个集合里则需要将这两个点联系起来。

关于联系起来后关系的变化,画几个图后发现还是异或。

为什么用0表示同类,1表示异类?画几个图发现这样表示关系变换最简单。

三、AC代码

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <fstream> using namespace std; const int MAXN = 2e3+;
int Par[MAXN];
bool Rank[MAXN]; void Init()
{
memset(Par, -, sizeof(Par));
memset(Rank, , sizeof(Rank));
} int Find(int x)
{
if(Par[x] == -)
return x;
int t = Par[x];
Par[x] = Find(Par[x]);
Rank[x] = Rank[t]^Rank[x];
return Par[x];
} int main()
{
//freopen("input.txt", "r", stdin);
int T, N, M;
scanf("%d", &T);
for(int Cnt = ; Cnt <= T; Cnt++)
{
if(Cnt!=)
printf("\n");
Init();
int x, y, fx, fy;
bool ans = true;
scanf("%d %d", &N, &M);
for(int i = ; i < M; i++)
{
scanf("%d %d", &x, &y);
if(ans)
{
fx = Find(x);
fy = Find(y);
if(fx == fy && Rank[x] == Rank[y])
{
ans = false;
}
else if(fx != fy)
{
Par[fx] = fy;
Rank[fx] = Rank[x]^(Rank[y]^);
}
}
}
if(ans)
{
printf("Scenario #%d:\nNo suspicious bugs found!\n", Cnt);
}
else
{
printf("Scenario #%d:\nSuspicious bugs found!\n", Cnt);
}
}
return ;
}

最新文章

  1. “.Net 社区虚拟大会”(dotnetConf) 2016 Day 2 Keynote: Miguel de Icaza
  2. iOS10 适配问题-Xcode8
  3. bzoj4555题解
  4. div样式text-align在子元素缩进不规范的情况下,chrome出现的问题(貌似结果是inline-block导致的)
  5. php解决中文截取乱码问题
  6. 使用jquery脚本获取随笔、文章和评论的统计数,自定义显示位置
  7. linux启动和关闭
  8. Ubuntu 和 Redhat / Fedora 服务管理命令对比表(附Fedora16新的服务管理工具systemctl )
  9. SQL语句中=null和is null
  10. spring容器IOC创建对象&lt;三&gt;
  11. Poj(2349),最小生成树的变形
  12. homework03
  13. C++函数模板本质-学习入门
  14. tomcat 系统架构与设计模式 第一部分 系统架构工作原理 转
  15. nginx的请求接收流程(一)
  16. linux cat more less head tail
  17. 冲刺NO.2
  18. GTX 750TI 使用 ffmpeg 时无法用 GPU HEVC(h.265) 进行加速
  19. MySQL-mysql 8.0.11安装教程
  20. Jmeter发送邮件功能SMTP Sampler

热门文章

  1. 固本培元之三:Convert、运算符、流程控制语句、ref/out/in三种参数类型
  2. 四.python数据类型,语句
  3. EKF model&amp;realization
  4. 构造方法概念,自定义构造(init)方法的用途, 类工厂方法(就是直接用类名 类调用)
  5. java中的监听事件
  6. Swing自定义JScrollPane的滚动条设置,重写BasicScrollBarUI方法
  7. swing中的分层
  8. ios7适配--隐藏status bar
  9. 编写高质量代码改善C#程序的157个建议——建议34:为泛型参数设定约束
  10. 我用Django搭网站(3)-表单RSA加密