算法 并查集
目录
前言
一 并查集的思路
二 并查集的代码分析
三 实操我们的代码
四 并查集的代码优化
总结
前言
并查集主要是用来求解集合问题的，用来查找集合还有就是合并集合，可以把这个运用到最小生成树里面
一 并查集的思路
1 并查集的相关的操作
👉1 查找
函数：find ( a )是用来查你需要查找的元素是在哪一个集合里面的
👉2 判断是否为同一个集合
函数：issamset( a, b )是用来判断你输入的数字是否在同一个集合里面
👉3 合并两个集合
函数：Iunion( a, b )是用来合并两个集合
2 并查集是怎么操作的
首先我们有很多个元素
首先可能不是很理解，我来解释一下
就是我们要找这个元素在哪一个集合，我没是不是很不好找，因为名字啥的啥也没有
所以我没就要对这个集合进行命名，才可以找到这个元素在哪里，才可以进行下面的操作
所以最重要的就是给这个集合进行命名
✅👉但是我们要怎么命名呢？
我们只需要找到这个集合里面的代表元素就好了，比如第一个集合的代表元素就是a
✅👉那么这个自环又是用来干什么的呢？
这个自环就是为了方便我没找到那个代表的元素的，你看我们找代表元素的时候，是要利用遍历的，所以当我们只有一个元素的时候，我们就可以进行遍历，遍历到自己了不就是自己就是代表元素么
✅👉如何进行合并操作呢？
首先我没看这个图，就是我没在进行合并的时候，我们先看这个元素个数的大小，我没不难发现，其实a和b都是一样的，所以就是随便a在b的下面或者b在a的下面都可以，最后b进行自环
✅👉如果两个进行合并呢？首先我们可以看每个集合的元素的个数，然后我们看都是2，那么代价都是一样的，所以我们可以b在d下面或者d在b下面，注意是头部和头部进行连接，别底部连接了，那就是错的
✅👉小挂大优化
小挂大的优化其实是用到这种一个比一个多的，那么就是小的挂在大的下面
好了我们介绍完了理论部分，接下来就是怎么用代码进行表示了
✅👉过程的分析
那么我们先画一下图来理解一下
首先我们用一个头部数组father来表示，他这个时候对应的头部是多少
用一个大小数组来表示这个时候这个集合有多大，上面是初始化
0 1合并
首先0的头部变成1了，但是1的头还是1，但是这个0的大小没有改变是因为这个已经没用了，用叉叉表示了，因为此时0不是头了，不再是代表数组
2 3合并
我们不难看到这个就是改变了头，这个3的头变成3了
4 5合并
跟上述一样的
2 4合并
我们不难看出这个就是把这个对应不是代表值的，直接标记为垃圾值
改变对应的头和大小就好了
1 5合并
最后我们就可以得出这个了
这个就是整个过程的分析
✅扁平优化
然后其实这里面也有一个扁平优化，就是在执行find的函数的时候，经过的节点直接放到头部
类似于这个图就是我们经过的路的节点不再指向上一个节点直接指向头，但是分支不是，就是例如a的分支不会指向头，除非经过它
扁平优化是一定要有的，小挂大可以没有
二 并查集的代码分析
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1000010; //long int n; //deputy array int father[N]; //children size array int Isize[N]; //stack int stack[N]; //lnitialize void bulid() { for (int i = 1; i <= n;i++) { father[i] = i; Isize[i] = 1; } } //find father way //里面有扁平化 int find(int x) { //沿途收集的点 int Ssize = 0; while (x != father[x]) { //收集节点 stack[Ssize++] = x; //继续往上走 x = father[x]; } //扁平化 //沿途已经收集好了，x已经跳到对应节点了 while (Ssize > 0) { father[stack[--Ssize]] = x; } return x; } //sameset way bool samset(int x, int y) { return find(x) == find(y); } //union way void Iunion(int x,int y) { int fx = find(x); int fy = find(y); //小挂大的优化 if (fx != fy) { if (Isize[fx] >= Isize[fy]) { //fx 代表大小 //fy也是大小 //在father数组里面改一下就是改了顶点 Isize[fx] += Isize[fy]; //modifty size father[fy] = fx; //modifty father } else { Isize[fy] += Isize[fx]; father[fx] = fy; } } } int main() { }代码对应的旁边是有解析的，读者可以看
我们来总结一下这个代码
首先我们有三个数组
👉1 father数组 2 size数组 3 stack数组
这三个数组分别用来存放头节点，集合大小，给find扁平化暂时放置元素
find函数在这里是尤为重要，因为它涉及了扁平化和每个函数都需要用到它
👉1 bulid数组就是初始化size数组和father数组，size用1初始化，father就是数字了，跟我上述说的思路是一样的
👉2 samset函数就是返回是否是一个集合只要看他们的头是不是一样的就好了，直接return 他们头部是否相等就好了，这个直接调用find函数
👉3 Iunion函数就是把这个数组取出来，我们除了大小要改变还要改变头部，我们可以用if语句来判断他们的头部是否相等，这个需要用到find函数，然后再进行大小化优化，大的放到小的小面就好了，这个也是用if语句进行判断
👉4 find数组就是查找了，注意要用到扁平操作，代码的操作的话就是，我们需要用到一个栈来进行存储我们路上所经过的数字，这个时候是不需要进行修改头部和大小的，因为不是合并，然后再进行扁平化操作，把路径的元素都放出来，连接到对应的头部
三 实操我们的代码
我们用一下我们上述的代码
这个是我们用上述代码进行实操的
代码的分析是跟上面一样的#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 100001000; //long int n; //deputy array int father[N]; //children size array int Isize[N]; //stack int stack[N]; //lnitialize void bulid() { for (int i = 1; i <= n; i++) { father[i] = i; Isize[i] = 1; } } //find father way //里面有扁平化 int find(int x) { //沿途收集的点 int Ssize = 0; while (x != father[x]) { //收集节点 stack[Ssize++] = x; //继续往上走 x = father[x]; } //扁平化 //沿途已经收集好了，x已经跳到对应节点了 while (Ssize > 0) { father[stack[--Ssize]] = x; } return x; } //sameset way bool samset(int x, int y) { return find(x) == find(y); } //union way void Iunion(int x, int y) { int fx = find(x); int fy = find(y); //小挂大的优化 if (fx != fy) { if (Isize[fx] >= Isize[fy]) { //fx 代表大小 //fy也是大小 //在father数组里面改一下就是改了顶点 Isize[fx] += Isize[fy]; //modifty size father[fy] = fx; //modifty father } else { Isize[fy] += Isize[fx]; father[fx] = fy; } } } int main() { int m; cin >> n >> m; bulid(); while (m--) { int z, x, y; cin >> z >> x >> y; if (z == 1) { Iunion(x, y); } else if (z == 2) { if (samset(x, y)) { cout << "Y" << endl; } else { cout << "N" << endl; } } } return 0; }
四 并查集的代码优化#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1000000; int father[N]; int n; void build() { for (int i = 0;i <= n;i++) { father[i] = i; } } int find(int x) { if (x != father[x]) { //递归的操作，学习过dfs都知道 father[x] = find(father[x]); } return father[x]; } bool semset(int x,int y) { return find(x) == find(y); } void Iunion(int x, int y) { //不管大小集优化了 father[find(x)] = find(y); } int main() { }这个代码的优化是用到了递归来解决的，注意不需要size数组是因为大挂小是一个不必须的操作，所以就不需要记录大小
👉判断是否在统一集合跟之前讲述的一样还是用return进行返回
👉查找
这个就是要进行扁平化。就是我们在搜索的过程中直接进行操作，而不是用一个stack进行存储，这个操作是需要进行递归的，就是在挖掘深度之后，进行回溯的时候把上一个深度的值进行赋值，然后最后在返回对应得头节点就好了
👉合并操作这个也很简单，就是把这个头给进行修改就好了，但是你需要判断是谁合并谁先
总结
我们主要讲述了并查集
并查集为什么叫并查集呢？
其实就是合并和查找在集合里面进行操作
然后我们涉及了几个功能就是查找，合并，判断是否在同一集合
这集合代码的实现和讲解在上面有