2 月 7 日算法练习- 数据结构-并查集

并查集

并查集是一种图形数据结构，用于存储图中结点的连通关系。
每个结点有一个父亲，可以理解为“一只伸出去的手”，会指向另外一个点，初始时指向自己。
一个点的根节点是该点的父亲的父亲的的父亲，直到某个点的父亲是自己根
当两个点的根相同时，我们就说他们是属于同一类，或者说是连通的。
如下：7、5、1、3、6的根都是3，所以他们是连通的，2、4是连通的，而2、6不连通，因为他们的根不同
在这里插入图片描述

找根

找根的方法是：
如果当前点不是根，就返回父亲的根。否则就是自己。
用递归的方法实现

int root(int x){if(pre[x]==x)return x;return root(pre[x]);
}

合并

在并查集中，所有的操作都在根上，假如我要使得x和y两个点合并，只需要将root(x)指向 root(y),或使得root(y)指向root(x)。 pre[root(x)]= root(y);
例如我要合并4和6.则需要将2指向3或将3指向2.
在这里插入图片描述

路径压缩

找根函数的复杂度最坏情况下会达到O（n），如果查询次数较多的话效率将会非常低下。
我们可以在找根的过程中，将父亲直接指向根，从而实现路径压缩，这样可以使得找根的总体时间复杂度接近O（1）。如下图，执行一次root（7）之后，沿途的点都会直接指向根3。

int root(int x){return pre[x] = (pre[x]==x?x:root(pre[x]));
}

在这里插入图片描述

蓝桥幼儿园

在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 2e5+9;
int pre[N],n,m;int root(int x){pre[x] = (pre[x]==x)?x:root(pre[x]);return pre[x];
}int main( ){cin>>n>>m;for(int i=1;i<=n;i++)pre[i]=i;while(m--){int op,x,y;cin>>op>>x>>y;if(op==1){pre[root(x)]=root(y);}else{if(root(x)==root(y))cout<<"YES"<<'\n';else cout<<"NO"<<'\n';}}return 0;
}

修改数组

在这里插入图片描述

思路：并查集的查询修改特性，根是未重复的数，非根是重复的数。初始化并查集 pre[i]=i表示每个根都未重复，遍历数组 a，遍历到 x 时将 x 修改为root(x) 的根，将 root(x) 指向 root(x+1) 的根，表示 x 的过去根已经重复，新根未重复。

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],pre[N];int root(int x){return pre[x] = (pre[x]==x)?x:root(pre[x]);
}int main( ){int n;cin>>n;for(int i=1;i<=N;i++)pre[i]=i;for(int i=1;i<=n;i++){cin>>a[i];a[i] = root(a[i]);pre[a[i]] = root(a[i]+1);}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[n==i];return 0;
}