[noip模拟]心<并查集>
2024-08-27 06:59:05
背景描述:
不是一切深渊都是灭亡
不是一切灭亡都覆盖在弱者的头上
——《这也是一切》 舒婷
有N个透明的盒子, 每个盒子里面有两个不同颜色的球, 总共有M种颜色。
Alice和Bob又在玩游戏, 具体的, Alice会从N个盒子里面选出若干个, Bob再从Alice选出的盒子里面选出一些(不能不选), 如果在Bob选出的盒子中, 每个颜色的球都总共出现了偶数次(0次也是偶数次), 那么Bob胜利, 否则Alice胜利
在Alice和Bob都足够聪明的情况下, Alice想知道自己在能够获胜的前提下, 第一次最多可以选出几个盒子
输入格式:
第一行有两个整数N和M, 意义如题
接下来N行, 第i+1行两个整数表示第i+1个盒子里面的两个球分别是什么颜色的
输出格式:
一行一个整数表示Alice最多可以选多少个盒子
样例输入:
3 3
1 2
2 3
2 3
样例输出:
2
数据规模:
对于30%的数据, N <= 10
对于50%的数据, N <= 20
对于100%的数据, N <= 100000, M <= 2N
可能是我太弱了,我虽然发现了是不能出现环,但是我还是打错了
这是一个并查集,我们把一个盒子的两个颜色看成是一条边连着的两个点,然后并查集组成链状结构
并查集的一个经典处理就是如果两个点不在一个集合就加进同一个集合,然后集合的表示就是这个点当前的祖先,如果开始判断这个点和这个点的祖先这条边时,就说明这条边成环了,就不要选
其实说白了就是一个裸的并查集操作
只是有一个小小细节就是不能单纯的fx=find(x),在这一步操作后,还要把fa[x]变成fx,不然会超时,毕竟这道题这看最终的祖先,途中的都不用管
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<iostream>
#define maxn 100005
using namespace std;
int n,m,fa[*maxn],ans;
int find(int x){
if(fa[x]==x)return x;
else return find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){fa[i]=i;}
for(int i=;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
fa[x]=find(x);fa[y]=find(y);
if(fx!=fy){
fa[fx]=fy;ans++;
}
}cout<<ans;
}
最新文章
- Constraint6:更新外键约束(Foreign Key Constraint)的引用列
- [Android Tips] 22. Available Java 7 Features in Android
- 操作系统开发系列—解释typedef void (*int_handler) ();
- MakeCode 递归生成资源文件
- HTML学习笔记——选择器
- [ThingWorx] Install PostgreSQL Issue
- LCLFramework框架之开发约束
- 画蛇添足-记spring3 hibernate4整合时遇到问题的处理办法
- spring中propertyplaceholderconfigurer简介
- 关于Java中计算日期差值不准确问题
- Java API —— 递归
- GoogLeNet学习心得
- 在html中禁用自己主动完毕
- 20_Android中apk安装器,通过WebView来load进一个页面,Android通知,程序退出自动杀死进程,通过输入包名的方式杀死进程
- go基础系列:简介
- SQL语法基础之INSEART语句
- 获得文件的CRC32值
- 生成器-代码举例:()和yield
- Docker技术入门与实战 第二版-学习笔记-8-网络功能network-1-单个host上的容器网络
- 软件工程实践-git的使用