并查集题目

并查集是一种十分常用并且好用的数据结构

并查集可以动态维护若干个不重叠的集合,支持合并与查询操作,是一种树形的数据结构


并查集的基础应用

村村通

对于这道题我们只需要求连通块的数量,然后将这几个联通快看成点,我们可以知道联通的n个点中最少有n-1边

#include <iostream>
#include <cstring>using namespace std;
const int N = 1010;
int p[N], st[N];int find(int x)
{if(x == p[x])   return x;return p[x] = find(p[x]);
}int main()
{// freopen("1.in", "r", stdin);while(1){memset(st, 0, sizeof st);int n, ans = 0;scanf("%d", &n);if(n == 0)  return 0;else{int m;  scanf("%d", &m);for(int i = 1; i <= n; ++ i)    p[i] = i;for(int i = 0; i < m; ++ i){int x, y;   scanf("%d%d", &x, &y);int a = find(x);int b = find(y);if(a != b)  p[a] = b;}for(int i = 1; i <= n; ++ i){int x = find(i);if(!st[x])  ans ++, st[x] = 1;;}cout << ans - 1 << endl;}}
}

带权并查集

推导部分和

这道题的是带边权并查集的应用,比较难想到的是建图

对于每个区间l, r,k, 我们可以由前缀和s[r] - s[l - 1] = k,我们从r连一条l-1的边

WechatIMG819.png

#include <iostream>using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
//p[N]数组用来做并查集
int p[N], n, m, q;
//s[N]数组是当前点到根结点的权值和,也是前缀和
LL s[N];//并查集的查询操作(带路径压缩)
int find(int x)
{if(x == p[x])   return x;else{int t = find(p[x]);s[x] += s[p[x]];p[x] = t;return t;}
}int main()
{// freopen("1.in", "r", stdin);cin >> n >> m >> q;for(int i = 1; i <= n; ++ i)    p[i] = i;for(int i = 0; i < m; ++ i){int l ,r;LL k; cin >> l >> r >> k;int t1 = find(l - 1), t2 = find(r);if(t1 != t2){p[t2] = t1;s[t2] = s[l - 1] - s[r] + k;}}while(q --){int l, r;cin >> l >> r;int t1 = find(l - 1), t2 = find(r);if(t1 != t2)    puts("UNKNOWN");else printf("%lld\n", s[r] - s[l - 1]);}return 0;
}

并查集的拓展域


例题团伙

#include <iostream>
using namespace std;
const int N = 2010;
int p[N];
bool st[N];
int find(int x)
{if(p[x] == x)   return p[x];return p[x] = find(p[x]);
}
void merge(int x, int y)
{int px = find(x), py = find(y);if(px != py)    p[px] = py;
}int main()
{// freopen("1.in", "r", stdin);int n, m;scanf("%d%d", &n, &m);for(int i = 1; i <= 2 * n; ++ i)    p[i] = i;for(int i = 0; i < m; ++ i){char op; int x, y;cin >> op >> x >> y;if(op == 'F'){merge(x, y);// merge(x + n, y + n);}else{merge(x + n, y);merge(x, y + n);}}// for(int i = 1; i <= n; ++ i)    cout << i << ' ' << find(i) << endl;    int cnt = 0;for(int i = 1; i <= n; ++ i)if(!st[find(i)]){cnt ++;st[find(i)] = 1;}cout << cnt << endl;return 0;
}

这是一道并查集的拓展域的题目也可以用带权并查集去做

本题和普通的并查集不同,普通并查集维护的是不相交集合,是一种传递性的关系如亲戚的亲戚是亲戚

本题是天敌的天敌是食物,是一种环形的关系

我们如果用拓展域来解决这道题目的话可以用3个并查集来维护3种关系,第一种是同类关系,第二种是食物关系,第三种是天敌

就本题而言我们不用真开三个并查集,我们可以将三个并查集开到一个数组里,下标的范围代表不同的集合

WechatIMG824.jpeg

#include <iostream>using namespace std;
const int N = 5e4 + 10;
int p[N * 3], ans, k, n;//1--n代表x的同类,n + 1 -- 2n代表x的食物, 2n + 1 -- 3n代表x的天敌
int find(int x)
{if(x == p[x])   return x;return p[x] = find(p[x]);
}
void merge(int x, int y)
{int px = find(x), py = find(y);p[py] = px;
}
int main()
{cin >> n >> k;for(int i = 1; i <= 3 * n; ++ i)    p[i] = i;for(int i = 0; i < k; ++ i){int d, x, y;scanf("%d%d%d", &d, &x, &y);if(x > n || y > n)  ans ++;//x、y是同类else if(d == 1){//如果根据前面的信息,我们可以知道y在x的食物域,//或者y在x的天敌域中,说明这句话是假话if(find(x + n) == find(y) || find(x + n + n) == find(y))    ans ++;//如果根据前面的信息,不能判断这句话是错误的,那么就讲这句话//当成对的并且更新x的三个域else{//y在x的同类域中merge(x, y);//y的食物和x的食物是同类merge(x + n, y + n);//y的天敌和x的天敌是同类merge(x + n + n, y + n + n);}}//如果x吃yelse{//若果y在x的同类域或者,y在x的天敌域说明这句话是假话if(find(x) == find(y) || find(x + n + n) == find(y))    ans ++;//这句话是真话就更新x的三个域else{//y在x的食物域中merge(x + n, y);//y的食物是x的天敌merge(x + n + n, y + n);//y的天敌是x的同类merge(x, y + n + n);}}}cout << ans << endl;return 0;
}

牛客修棋盘

我们通过观察可以知道,走到每个点的奇偶性是确定的

同时我们的合法状态只有两种


如果我们对每个点都修改的话,我们能达到的状态如下:

所以我们每次修改次数最少的话应该是考虑我们每个点都修改的状态,当我们把每个点都修改的话就是互补的一个状态

#include <iostream>
#include <queue>#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 1010;
int res, n, m;
char g[N][N];
bool st[N][N];int main()
{cin >> n >> m;for(int i = 1; i <= n; ++ i)for(int j = 1; j <= m; ++ j){char ch; cin >> ch;int x = ch -'0';if((i + j) % 2 == 0 && x == 1)    res ++;if((i + j) % 2 && x == 0)    res ++;}if(res == m * n)    puts("0");else    cout << res << endl;return 0;
}

P5937 [CEOI1999] Parity Game

题目的具体思路如下:考虑一段连续区间的1个数的奇偶,可以转化为考虑考虑两个端点前缀和的奇偶性上,分为两种情况,如果[l, r]区间内1的个数为偶数,说明sum[r]和sum[l - 1]包含1的个数的奇偶性相同,反之若为奇数则两个包含1的个数的奇偶性相反,我们知道奇偶性具有传递性,这样我们就可以种类并查集来维护,注意n的范围比较大,但是实际的需要用到的点的个数是比较小的,这里我们需要离散化一下。

#include <bits/stdc++.h> 
#define LL long long 
using namespace std;const int N = 1e4 + 10;
int p[N * 2 + 10], n, m, k;
map<int, int>mp;
int b[N * 2];struct wy
{int l, r, op;	
}q[N];int find(int x)
{if(x != p[x])	p[x] = find(p[x]);return p[x];
}void merge(int x, int y)
{int px = find(x), py = find(y);p[py] = px;
}int query(int x)
{return lower_bound(b + 1, b + 1 + k, x) - b;
}
void solve()
{scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++ i){int l, r, op;char s[5];scanf("%d%d%s", &l, &r, s);if(s[0] == 'e')	op = 1;else op	= 2;q[i] = {--l, r, op};b[++ k] = l;b[++ k] = r;} sort(b + 1, b + 1 + k);k = unique(b + 1, b + 1 + k) - (b + 1);for(int i = 1; i <= 2 * k; ++ i) p[i] = i;for(int i = 1; i <= m; ++ i){int l = query(q[i].l), r =  query(q[i].r), op = q[i].op;if(op == 1) {if(find(l) == find(r + k) || find(r) == find(l + k)){printf("%d", i - 1);return;}else{merge(l, r);merge(l + k, r + k);}}else{if(find(l) == find(r) || find(r + k) == find(l + k)){printf("%d", i - 1);return;}else{merge(l, r + k);merge(r, l + k); 	}}	}printf("%d", m);
}
int main()
{
//	freopen("1.in", "r", stdin);solve(); return 0;
}

P1955 [NOI2015] 程序自动分析

这道题目是相等关系,相等关系也具有传递性,明显我们可以用并查集来维护。
我们可以先对处理相等,然后去查询不相等的是否在一个集合里面如果在一个集合里面则说明这样的点是不存在的。这道题目的数据的范围很大,但实际用到的很少,我们需要对数据进行离散化。

#include <bits/stdc++.h> 
#define LL long long 
using namespace std;const int N = 1e6 + 10;
int n, m, p[N], a[N], k, tot;
struct wy{int x, y, e;
}q[N];int find(int x)
{if(x != p[x])	p[x] = find(p[x]);return p[x];
} void merge(int x, int y)
{int px = find(x), py = find(y);p[py] = px;
}void solve()
{scanf("%d", &n);for(int i = 1; i <= n; ++ i){int x, y, e;scanf("%d%d%d", &x, &y, &e);a[++ tot] = q[i].x = x;a[++ tot] = q[i].y = y;q[i].e = e;	}sort(a + 1, a + 1 + tot);tot = unique(a + 1, a + 1 + tot) - a - 1;for(int i = 1; i <= tot; ++ i)	p[i] = i;for(int i = 1; i <= n; ++ i){q[i].x = lower_bound(a + 1, a + tot + 1, q[i].x) - a - 1;q[i].y = lower_bound(a + 1, a + tot + 1, q[i].y) - a - 1;if(q[i].e == 1){merge(q[i].x, q[i].y);}}for(int i = 1; i <= n; ++ i){int x = q[i].x;int y = q[i].y;if(q[i].e == 0 && find(x) == find(y)){puts("NO");return;}}puts("YES");
}int main()
{
// 	freopen("1.in", "r", stdin);scanf("%d", &k);while(k--) solve(); return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/139950.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【华为云云耀云服务器L实例评测|云原生】自定制轻量化表单Docker快速部署云耀云服务器

&#x1f935;‍♂️ 个人主页: AI_magician &#x1f4e1;主页地址&#xff1a; 作者简介&#xff1a;CSDN内容合伙人&#xff0c;全栈领域优质创作者。 &#x1f468;‍&#x1f4bb;景愿&#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长&#xff01;&#xff01;&…

笔记2.2:网络应用基本原理

一. 网络应用的体系结构 &#xff08;1&#xff09;客户机/服务器结构&#xff08;Client-Server, C/S&#xff09; &#xff08;2&#xff09;点对点结构&#xff08;Peer-to-Peer&#xff0c;P2P&#xff09; &#xff08;3&#xff09;混合结构&#xff08;Hybrid&#x…

大数据学习技术栈及书籍推荐

作为一名开发人员&#xff0c;特别是后端开发人员&#xff0c;随着网络数据量的持续增长&#xff0c;拥有强大的大数据处理能力已经成为每个公司或产品&#xff08;尤其是2C业务&#xff09;的必备条件。以下是我在网络上搜集和自身研究的基础上&#xff0c;为您推荐的技术栈和…

【python】Seaborn画热力图,只显示第一行数字---seaborn与matplotlib版本问题

github上有这个讨论&#xff1a;Heatmap only has annotation text in the top row only Issue #3478 mwaskom/seaborn (github.com)翻译过来就是&#xff1a;热图仅在最上面一行有注释文本&#xff1b; 原因就是matplotlib 在2023年9月更新到了 3.8.0版本&#xff0c;改变了…

大数据Flink(八十三):SQL语法的DML:With、SELECT WHERE、SELECT DISTINCT 子句

文章目录 SQL语法的DML:With、SELECT & WHERE、SELECT DISTINCT 子句 一、DML:With 子句

c语言 static

1、静态局部变量在程序加载时初始化&#xff0c;静态局部变量的初始值写入到了data段&#xff1a; 如下代码test_symbol.c int f() {static int x 0;return x; }int g() {static int x 9;return x; }使用命令gcc -c test_symbol.c -o test_symbol 编译 使用命令 readelf -a …

Web ui自动化测试框架总结

【软件测试面试突击班】如何逼自己一周刷完软件测试八股文教程&#xff0c;刷完面试就稳了&#xff0c;你也可以当高薪软件测试工程师&#xff08;自动化测试&#xff09; 实施过了web系统的UI自动化&#xff0c;回顾梳理下&#xff0c;想到什么写什么&#xff0c;随时补充。 首…

数据分享|R语言逻辑回归、线性判别分析LDA、GAM、MARS、KNN、QDA、决策树、随机森林、SVM分类葡萄酒交叉验证ROC...

全文链接:http://tecdat.cn/?p27384 在本文中&#xff0c;数据包含有关葡萄牙“Vinho Verde”葡萄酒的信息&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 介绍 该数据集&#xff08;查看文末了解数据获取方式&#xff09;有1599个观测值和12个变量&#xf…

windows安装c环境

一. 下载安装mingw-w64 mingw-w64 解压后放到window环境变量路径 sysdm.cpl参看是否安装成功 二. 安装c idea Dev-Cpp下载及安装 新建文件 运行 编译&#xff08;F9&#xff09;、运行&#xff08;F10&#xff09;以及编译运行&#xff08;F11&#xff09; 参考 安装C…

Guava Cache介绍-面试用

一、Guava Cache简介 1、简介 Guava Cache是本地缓存&#xff0c;数据读写都在一个进程内&#xff0c;相对于分布式缓存redis&#xff0c;不需要网络传输的过程&#xff0c;访问速度很快&#xff0c;同时也受到 JVM 内存的制约&#xff0c;无法在数据量较多的场景下使用。 基…

图像处理之频域滤波DFT

摘要&#xff1a;傅里叶变换可以将任何满足相应数学条件的信号转换为不同系数的简单正弦和余弦函数的和。图像信号也是一种信号&#xff0c;只不过是二维离散信号&#xff0c;通过傅里叶变换对图像进行变换可以图像存空域转换为频域进行更多的处理。本文主要简要描述傅里叶变换…

Spring面试题11:什么是Spring的依赖注入

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:说一说Spring的依赖注入 依赖注入(Dependency Injection)是Spring框架的一个核心特性,它是指通过外部容器将对象的依赖关系注入到对象中,从而…

win10 关闭edge跳转IE浏览器

按下windows键&#xff0c;搜索控制面板 右上角输入IE 点击IE 高级中取消下红框选择即可

接口自动化测试之Requests模块详解

Python中&#xff0c;系统自带的urllib和urllib2都提供了功能强大的HTTP支持&#xff0c;但是API接口确实太难用了。Requests 作为更高一层的封装&#xff0c;在大部分情况下对得起它的slogan——HTTP for Humans。 让我们一起来看看 Requests 这个 HTTP库在我们接口自动化测试…

Spring面试题15:Spring支持几种bean的作用域?singleton、prototype、request的区别是什么?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring支持几种bean的作用域? Spring支持以下几种Bean的作用域: Singleton(单例):这是Spring默认的作用域。使用@Scope(“singleton”)注解或…

web前端的float布局与flex布局

flex布局 <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>flex</title><style>.container{width: 100%;height: 100px;background-color: aqua;display: flex;flex-direction: row;justify-content: space-ar…

使用 rtty 进行远程 Linux 维护和调试

rtty 是一个用于在终端上进行远程连接和数据传输的工具。它提供了一种简单的方式来与远程设备进行通信&#xff0c;使得在不同主机之间传输数据变得更加方便。 安装 rtty 是一个可执行程序&#xff0c;可以在 Linux、macOS 和 Windows 等平台上使用。 Linux/macOS 在终端中执…

web二级操作题

js和css的引入 在 HTML 中&#xff0c;你可以使用 <script> 和 <link> 标签来引入外部的 JavaScript 文件和 CSS 文件。 引入外部的 JavaScript 文件&#xff1a; <script src"path/to/script.js"></script>src 属性指定了 JavaScript 文…

Oracle for Windows安装和配置——Oracle for Windows数据库创建及测试

2.2. Oracle for Windows数据库创建及测试 2.2.1. 创建数据库 1&#xff09;启动数据库创建助手&#xff08;DBCA&#xff09; 进入%ORACLE_HOME%\bin\目录并找到“dbca”批处理程序&#xff0c;双击该程序。具体如图2.1.3-1所示。 图2.1.3-1 双击“%ORACLE_HOME%\bin\dbca”…

浅谈SpringMVC的请求流程

目录标题 浅谈SpringMVC的请求流程SpringMVC的介绍SpringMVC的逻辑概念运行图解知识总结 浅谈SpringMVC的请求流程 对于SpringMVC而言重点是了解它的底层运行逻辑&#xff0c;从而可以根据其逻辑来进行实际业务的操作或者是利用原理增强业务的功能性&#xff0c;最终达到项目预…