CF1012B Chemical table
2024-10-10 03:16:38
给你一个 \(n\times m\) 的矩形,一开始有 \(q\) 个格子上被标记。对于任意两行两列,如果交汇的四个格子中有三个被标记,那么第 \(4\) 个会被自动标记。问你至少需要手动标记几个格子,使得整个矩形内的格子都被标记。
\(n,\ m,\ q\leq2\times10^5\)
并查集,构造
把元素 \((x,\ y)\) 看做二分图的一条边 \((x,\ n+y)\)
目标是将它变成完全二分图
而标记其他点的条件 \((x_1,\ y_1),\ (x_1,\ y_2),\ (x_2,\ y_1)\to(x_2,\ y_2)\) 并不改变二分图中连通分量个数
所以对于二分图的某一个连通分量必定可以通过如上条件变成一个完全二分子图
所以答案即为联通所有连通分量的边数,即为 \(\verb|连通分量个数|-1\)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int n, m, q, ans, par[maxn];
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(int x, int y) {
if ((x = find(x)) != (y = find(y))) {
par[x] = y, ans++;
}
}
int main() {
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n + m; i++) {
par[i] = i;
}
while (q--) {
int x, y;
scanf("%d %d", &x, &y);
unite(x, n + y);
}
printf("%d", n + m - ans - 1);
return 0;
}
\(orz\ \color{black}{P}\color{red}{inkrabbit}\)
最新文章
- iOS之访问权限以及跳转到系统界面
- 怎么使用Delphi获取当前的时间,精确到毫秒
- Crystal Reports 2008(水晶报表) JDBC连接mysql数据库
- SVN服务器搭建和使用(一)(转载)
- 赋值,copy和deepcopy
- 【记录】在MAC上安装caffe
- 蓝桥网试题 java 基础练习 字母图形
- 201521123091 《Java程序设计》第4周学习总结
- 201521123109《java程序设计》第九周学习总结
- DOM 遍历-同胞
- 基于hi-nginx的web开发(python篇)——动态路由和请求方法
- 浅析关于java的一些基础问题(上篇)
- Python Docker 查看私有仓库镜像【转】
- 浅谈jquery事件命名空间
- jQuery 购物车
- Js 转动抽奖实现
- Python(x,y) 的 FTP 下载地址
- nodejs之glob与globby
- c#中base64加密解密
- Java-动态代理技术