并查集与二分算法

并查集

• 合根植物：合根植物 - 蓝桥云课 (lanqiao.cn)

并查集的基本概念

并查集（Disjoint Set）是一种非常常用的数据结构，主要用来处理一些不相交集合（Disjoint Set）的合并及查询问题。它支持以下两种操作：

1. 查找（Find）：确定某个元素属于哪个子集。它可以被用来确定两个元素是否属于同一个子集。

2. 合并（Union）：将两个子集合并成同一个集合。

并查集可以使用数组或者树实现，其中数组实现较为简单，但是效率稍低；树实现较为复杂，但是效率较高。

• 并查集是大量的树（单个节点也，算是树）经过合并生成一系列家族森林的过程。

• 每个集合也就是每棵树都是由根节点确定，也可以理解为每个家族的族长就是根节点。

我们维护一个parent数组，每个元素初始化为对应的数组下标，代表自己是独立的一棵树，且是树根。以第一棵树为例，在后续数据处理过程中，我们把与所有与"2"同属一个连通分量的元素都连到"2"上，并把数组对应下标的元素赋值为2，其中"5"先连接到了"1"上，"1"又连接到了"2"上。最后，数组每个元素都代表其指向的父节点。

并查集的存储：

parent.resize(n);
for (int i = 0; i < n; ++i) {
    parent[i] = i;
}

并查集的查询：

int find(int x){
    if(parent[x] == x)
    	return x;
    else
    	return find(parent[x]);
}

并查集的路径压缩：

// 彻底的路径压缩
// 查找元素x所在的集合编号
int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

图解：

并查集的集合合并：

// 合并元素x和元素y所在的集合
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

图解：

以下是使用C++数组实现的并查集存储，查询和合并操作：

#include <iostream>
#include <vector>

using namespace std;

// 并查集类
class UnionFind {
public:
    // 构造函数，传入集合中元素数量n
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // 查找元素x所在的集合编号
    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并元素x和元素y所在的集合
    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

private:
    vector<int> parent; // 存储每个元素所在的集合编号
};

其中，parent 数组用来存储每个元素所在的集合编号。初始化时，每个元素的父节点都是自己。查询操作使用了路径压缩优化，将树高度降低，加速后续查询操作。合并操作只需要将元素 x 所在的集合的根节点指向元素 y 所在集合的根节点即可。

使用该并查集类可以进行以下操作：

int main() {
    UnionFind uf(10); // 创建一个包含10个元素的并查集

    uf.unionSet(0, 1);
    uf.unionSet(2, 3);
    uf.unionSet(4, 5);
    uf.unionSet(6, 7);
    uf.unionSet(8, 9);
    uf.unionSet(0, 2);
    uf.unionSet(4, 6);
    uf.unionSet(0, 4);

    cout << uf.find(1) << endl; // 输出：2
    cout << uf.find(5) << endl; // 输出：6

    return 0;
}

上述代码实现了一个包含10个元素的并查集，先将几个元素单独构成集合，然后再将一些集合合并起来。最后输出了两个元素属于哪个集合。

• 主要参考：ChatGPT

• 部分参考：(107条消息) 图解并查集_1加一的博客-CSDN博客

二分算法

• 跳石头：跳石头 - 蓝桥云课 (lanqiao.cn)

二分的基本思想

图解：

二分法的两种实现代码：

// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继） 
while(low<high){
    int mid = (low + high)/2;
    if(a[mid]>=x){
        high = mid;
    }else{
        low = mid + 1;
    }
}
// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前趋）
while(low<high){
    int mid = (low + high + 1)/2;
    if(a[mid]<=x){
        low = mid;
    }else{
        high = mid - 1;
    }
}

实数二分

根据前面的知识，我们要找到一个具有单调性的数列，去二分。这个题的关键是我们要去二分什么，这里可以二分的是 a^M 中的 a ，所以我们要先想办法设计出用于处理实数二分的代码。——也就是判断 N 与 a^M 的大小关系

实数二分的算法模板：

// 模版一：实数域二分，设置eps法
// 令eps为小于题目精度一个数即可。比如题目说保留4位小数，0.0001这种的。那么eps就可以设置为五位小数的任意一个数0.00001-0.00009等等都可以。
// 一般为了保证精度我们选取精度/100的那个小数，即设置eps=0.0001/100=1e-6
while (l+eps<r){
    double mid = (l+r)/2;
    if (pd(mid))
    	r = mid;
    else
    	l = mid;// 注意这里和传统的二分法不同
}

// 模版二：实数域二分，规定循环次数法
// 通过循环一定次数达到精度要求，这个一般1og2N<精度即可。N为循环次数，在不超过时间复杂度的情况下，可以选择给N乘一个系数使得精度更高。
for (int i=0;i<100;i++){
    double mid = (l+r)/2;
    if (pd(mid))
    	r = mid;
    else
    	l = mid;// 注意这里和传统的二分法不同
}

核心pd算法：

bool pd(double a,int m)
{
    double c = 1;
    while(m>0)
    {
        c = c*a;
        m--;
    }
    if(c>=n)
    	return true;
    else
    	return false;
}

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 实数二分题 

int n, m;// 分别为实数n与m次根号下，即求m次根号下的n的值为多少？ 
double eps = 1e-8; // 因为题目中要求保留7位小数 

bool pd(double a, int m){// 用 a^m 与 n 进行比较
	int c = 1;
	while(m>0){
		c = c*a;
		m--;
	} 
	if(c>=n)// a^m大于n，那么表明a大了，应该减小一点 
		return true;
	else
		return false;
}

int main() {
	cin>>n>>m;
	double L = 0, R = n;
	while(L + eps < R){// 以eps精度进行二分处理 
		double mid = (L+R)/2;
		if(pd(mid, m)){
			R = mid;
		}else{
			L = mid;// 注意这里和传统的二分法不同
		}
	} 
	printf("%.7f", L);// 涉及到输入输出精度的使用C的标准输入输出更好 
	return 0;
}

二分法习题

题目+编号	题目+编号
扫地机器人 199	区间移位 111
求立方根 1217	高精度开根 909
“123” 1591	二分法查找数组元素 1389
A Careful Approach 1390	求阶乘 2145
最少刷题数 2143	最大子矩阵 2147
青蛙过河 2097