POJ_2492 A Bug's Life 【并查集】
2024-08-25 14:28:30
一、题面
二、分析
并查集判断类别的题目感觉套路都差不多。
还是先判断在不在一个集合里,在一个集合里才能判断是否同类。
若不在一个集合里则需要将这两个点联系起来。
关于联系起来后关系的变化,画几个图后发现还是异或。
为什么用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 ;
}
最新文章
- “.Net 社区虚拟大会”(dotnetConf) 2016 Day 2 Keynote: Miguel de Icaza
- iOS10 适配问题-Xcode8
- bzoj4555题解
- div样式text-align在子元素缩进不规范的情况下,chrome出现的问题(貌似结果是inline-block导致的)
- php解决中文截取乱码问题
- 使用jquery脚本获取随笔、文章和评论的统计数,自定义显示位置
- linux启动和关闭
- Ubuntu 和 Redhat / Fedora 服务管理命令对比表(附Fedora16新的服务管理工具systemctl )
- SQL语句中=null和is null
- spring容器IOC创建对象<;三>;
- Poj(2349),最小生成树的变形
- homework03
- C++函数模板本质-学习入门
- tomcat 系统架构与设计模式 第一部分 系统架构工作原理 转
- nginx的请求接收流程(一)
- linux cat more less head tail
- 冲刺NO.2
- GTX 750TI 使用 ffmpeg 时无法用 GPU HEVC(h.265) 进行加速
- MySQL-mysql 8.0.11安装教程
- Jmeter发送邮件功能SMTP Sampler
热门文章
- 固本培元之三:Convert、运算符、流程控制语句、ref/out/in三种参数类型
- 四.python数据类型,语句
- EKF model&;realization
- 构造方法概念,自定义构造(init)方法的用途, 类工厂方法(就是直接用类名 类调用)
- java中的监听事件
- Swing自定义JScrollPane的滚动条设置,重写BasicScrollBarUI方法
- swing中的分层
- ios7适配--隐藏status bar
- 编写高质量代码改善C#程序的157个建议——建议34:为泛型参数设定约束
- 我用Django搭网站(3)-表单RSA加密