何为并查集？

本文主要是介绍何为并查集？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是并查集？

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。简单来说，并查集是用来管理元素分组的算法。

并查集的作用是什么？

并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。

以下列例题来具体阐述：

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

假设我们有3个人x,y,z

假设x打赢y，a[y]=x；

也就是说x是y的老大

假设z打赢x，那么a[x]=z;

z也就是x的老大，同时x是y的老大，那么z必然也是y的老大

这题求的是两个数是否在同一集合，那么我们只需要比较是否是同一个老大即可。

首先，我们先让所有元素都成为自己的老大，也就是：

for(int i=1;i<=n;++i) a[i]=i;

接着定义查找函数,然后进行路径压缩（简单来说就是直接让y的老大指向z，跳过中间其他的父节点），最后按题意读入即可，详细细节看代码。

实现代码：

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
using namespace std;
const int N=1e4+5;
int a[N];
int find(int x){//查找函数if(a[x]==x) return x;//若找到老大，直接返回else{return a[x]=find(a[x]);//等价于a[x]=find(a[x]);//将z中间所有的父节点都变为y//     return a[x];//接着继续找z包含的父节点，直到找到空为止（也就是找到根节点结束）}
}
void solve(){int n,m;cin >> n >> m;for(int i=1;i<=n;++i) a[i]=i;//让自己成为自己的老大while(m--){int x,y,z;cin >> x >> y >> z;if(x==1){a[find(z)]=find(y);//直接定义y一定打赢z，所以z的老大一定是y，那么就直接将z的老大指向y的老大即可}else{if(find(y)==find(z)){//若老大相同cout << "Y" << endl;}else cout << "N" << endl;}}return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;//cin >> t;//while(t--) solve();return 0;
}

这篇关于何为并查集？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---