并查集
算法初见：并查集
这是一个类似于树的，可以将两个元素合并起来的一种数据结构。 —-作者感觉的，(●ˇ∀ˇ●)
并查集的基本功能
今天，我们来看看并查集这么一个数据结构，来介绍一下它的基本功能
并查集的主要作用就是把两个树合并成一个树，但是，如果只是这么说的话，那就太笼统了，别人这么跟我说，我也不知道是什么意思，所以下面我们就来好好聊聊合并成一棵树，首先，我们来画个图，从图里面来了解这么一个数据结构
两棵树，生成！
子树1 子树2
3 5
2 4 1
1 5 3 8 1 3 6注意，这两棵树可以不是二叉树，比如子树2就不是二叉树
现在，我们来看看这两棵树的共同点，比如说，每一棵树都有自己的根节点，子树1的根节点是3，子树2的根节点是5，每一个根节点都会生成任意数的子节点(只要不是负数)，每一个子节点都会生成任意数的自己的子节点，这么依次下去，而并查集做的，就是把两棵本来毫无关系的树变成一棵树，那么，该怎么变成一棵树呢？
其实，很简单，就是把其中一棵树的根节点移到另外一棵树上，像这样，我们把子树1的根节点移动到子树2上
子树3
5
1 3
1 3 6 2 4
1 5 3 8现在的子树3就是由子树1和子树2合成的一棵新的树
由于两棵树合成一棵树，所以它们肯定要保留一个根节点，在子树3里面，保留的是子树2的根节点，也就是让子树1的所有元素的根节点变成子树2的根节点
这样一来，我们也可以来解释子树1和子树2的生成关系了，子树1是由3，2，4，1，5，3，8这几个子子树构成的，而子树2是由5，1，1，3，6这些子子树构成的，对于每一个节点，我们要找到这个节点的根节点，那就是先找到这个节点的父节点，再找到这个父节点的父节点，直到找到最后的根节点
好了，现在我们已经知道了并查集的基本作用了，就是将两个节点不断地合并，变成一棵新的树，下面我们来通过一道例题，来从代码的实现上来更好的了解并查集
下题来自acwing算法基础课
题目：合并集合
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n, m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例：
Yes
No
Yes算法分析
其实，这道题就是一道很经典的并查集的题目，里面的a, b本来自生就是一颗小树，现在要把两棵树合并，是这棵树变得更大
首先，先初始化
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int p[N];区间压缩
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}这时候，我们来介绍一下p[N]数组和find(x) 这两个操作
首先，我们在一开始的时候，每一个a, b都作为一个个体，那么我们就假设它们的根节点就是它们自己，所以就可以
for(int i = 0;i < n;i++) {
p[i] = i;
}在一开始，就对我们的p[i]进行初始化, 然后我们再来根据题目，改变一个个个体
然后呢，区间压缩就是一个特别厉害的加速算法了，在一开始介绍并查集的时候，我们有一个查询操作，在我们查询每一个节点的根节点的时候，要先找到这个节点的父节点，这样依次寻找出来，但是如果每次都要这么查询的会很慢，所以通过这个区间操作，对于节点找到根节点上的所有点，我们通过回溯统一赋值为根节点，那么就只要查询一次，就可以记录了
下面是输入操作
int n, m;
cin >> n >> m;
for(int i = 1;i <= n;i++) p[i] = i;
for(int i = 1;i <= m;i++) {
char ch[2];
int a, b;
scanf("%s%d%d", ch, &a, &b);
//问题解决()
}下一步，我们来讨论题目中的两种情况，先是第一种
if(ch[0] == 'M') p[find(a)] = find(b);对于两个数，我们先找到各自的根节点(区间压缩后的复杂度是O(1)的)，然后我们默认让b的根节点变成a的根节点，就类似于a是子树1，b是子树2，我们把a移植到b上
第二种
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;这种其实就很简单了，就是询问两个数值的根节点是否相等，直接区间压缩一下就可以了
总代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1;i <= n;i++) p[i] = i;
for(int i = 1;i <= m;i++) {
char ch[2];
int a, b;
scanf("%s%d%d", ch, &a, &b);
if(ch[0] == 'M') p[find(a)] = find(b);
else {
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}从这道题上，完美体现了并查集的两个基本操作了，我们再来看看一道进阶题(其实难度也是简单hh)
题目：连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点a和点b之间连一条边，a和b可能相等；Q1 a b，询问点a和点b是否在同一个连通块中，a和b可能相等；Q2 a，询问点a所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例：
Yes
2
3算法分析
这道题跟第一题相比，其实就多了一个判断连通块中点的数量，如题目标题所说，那么，其实我们只要再添加一个数组用来记录每一个数所在的树里面的节点的个数就好了，初始值就设置为1
首先，初始化 + 区间压缩
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int p[N], sum[N];
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1;i <= n;i++) p[i] = i, sum[i] = 1;
for(int i = 1;i <= m;i++)
{
string s;
int a, b;
cin >> s;
//条件判断
}
return 0;
}然后，就是对于三种情况进行分别的判断了
第一种情况，在a和b之间连一条边，a和b可能相等
那么也就是说，a和b可能是在一个根节点里面，在一个根节点的话就不用管了，那我们的判断条件就是看它们的根节点是否相等
if(s == "C") {
cin >> a >> b;
//找到a和b各自的根节点
a = find(a), b = find(b);
//如果根节点不同
if(a != b) {
//让a的根节点改变
p[a] = b;
//b所在的数里面的总的点数加上原来a所在的树里面的节点数
sum[b] += sum[a];
}
}第二种情况，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等
同理，只要看看a和b的根节点是否一样就可以了
else if(s == "Q1") {
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}第三种情况，询问点 a 所在连通块中点的数量
那么就是输出a所在树的点的数量
else {
cin >> a;
cout << sum[find(a)] << endl;
}总代码
if(s == "C")
{
cin >> a >> b;
a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
sum[b] += sum[a];
}
}
else if(s == "Q1")
{
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
else
{
cin >> a;
cout << sum[find(a)] << endl;
}好了，既然已经写了两道题了，想必大家已经理解了并查集了吧，现在我们再来写一道简单题，(●ˇ∀ˇ●)
题目：超市
超市里有 N 件商品，每件商品都有利润 pi 和过期时间 di，每天只能卖一件商品，过期商品不能再卖。
求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
输入格式
输入包含多组测试用例。
每组测试用例，以输入整数 N 开始，接下来输入 N 对 pi 和 di，分别代表第 i 件商品的利润和过期时间。
在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。
输出格式
对于每组产品，输出一个该组的最大收益值。
每个结果占一行。
数据范围
0≤N≤10000,
1≤pi, di≤10000
最多有 14 组测试样例
输入样例：
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10输出样例：
80
185算法分析
浅看这道题，大致就可以分析出来，这道题考了贪心，我们要找在不过期的情况下的能够卖的最贵的物品，而且物品的价格与过期天数可以组成对组，我们可以考虑建立对组来写，而这道题会有多组输入，所以如果一个个判断会超时，所以我们采取并查集，对于每一个天数，都看成一棵树，当有超过一天的树被用过了后，就用并查集把用过的天数联系起来，这样可以更加方便查找我们没有用过的天数
总代码
首先初始化
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
vector<PII> res;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}输入
int main()
{
int n;
while(cin >> n)
{
//清空对组
res.clear();
//maxx记录最后一天
int ans = 0, maxx = 0;
for(int i = 0;i < n;i++)
{
int a, b;
cin >> a >> b;
//对组默认的排序是从小到大，那么都开成负号的，再反过来就是从大到小了
res.push_back({-a, b});
maxx = max(maxx, b);
}
for(int i = 0;i <= maxx;i++) p[i] = i;
//对组排序
sort(res.begin(), res.end());
//算法实现()
cout << ans << endl;
}
return 0;
}算法实现
//遍历res对组，由re记录
for(auto re: res) {
//刚刚是通过负号排的序
int l = -re.first, r = re.second;
//找到这一天的根节点
int pt = find(r);
//如果还有天数没有被使用
if(pt > 0) {
//总数增加
ans += l;
//改变这一天的根节点与上一天的节点相连
p[pt] = pt - 1;
}
}课后练习
P1230 智力大冲浪(复习)
P1230 智力大冲浪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
涉及算法：贪心 结构体排序 并查集 二叉堆
注：这道题就是超市那道题的简单版，就相当于背板子喽
