大佬教程收集整理的这篇文章主要介绍了【数据结构】并查集，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
先看一道题：假如已知有n个人和m对好友关系（存于数组r），如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们是属于同一个朋友圈，请写程序求出n个人里一共有多少个朋友圈。
例如：n=5,m=3,r={{1,2},{2,3},{4,5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1,2,3属于一个朋友圈，4,5属于一个朋友圈，结果为2个朋友圈。
第一种方法：我们可以创建3个set——s1,s2,s3对应3对关系，分别在s2和s3中查找s1中的0和1，如果找到了，将s2中的元素插入s1中，并清空s2；统计非空set的个数，即可得到朋友圈的个数。
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。并查集是一种树型的数据结构，用于处理一些不想交的集合的合并及查询问题。在使用中，常常以森林来表示。
每一个集合以一颗树来表示，树的每一个结点代表集合的一个元素，开始时，每个元素是一个自己的集合，因此是一个森林。类似堆，我们用一个数组的下标表示元素名，第i个数组元素代表它所在的集合的根结点。树的根结点的下标代表集合名称，根结点的值表示集合中元素个数。
主要操作有：
举一个例子：
假设一个集合s为：s={0,1,3,4,5,6,7,8,9}。
1》初始化：我们全部用-1初始化每一个树的根结点
| -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
2》合并成以下3个集合：
s1={0,6}; s2={1,8}; s3={2,9};
其树形结构如下：
按照上面树的结构，假设我们的数组名为a，我们需要执行的操作是，a[0]=a[0]-a[3](因为是负数，所以需要减操作); a[3]=0(3的父结点);
以此类推，我们可以得到这样的数组：
| -5 | -3 | -2 | 0 | 0 | 0 | 0 | 1 | 1 | 2 |
我们可以发现，数组中的负数的绝对值表示的是集合中元素的个数；负数的个数表示集合的个数；非负的数字表示的其下标对应的父结点。
3》假如要将6对应的集合与9对应的集合合并。应该怎么做？
首先，判断6和9对应的父结点是不是同一个结点，如果是同一个，则说明他们本身就在同一个集合中；如果不是同一个，则先找到6和9的父结点——0和2，再执行a[0]=a[0]-a[2]; a[2]=0(2的父结点);
此时数组变为：
| -7 | -3 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 |
并查集的代码如下：
#include <iostream>
#include <vector>
using namespace std;
class UnionFind
{
public:
UnionFind(size_t sizE)
: _set(size,-1)//构造函数
{
// _set.resize(size,-1);//用-1初始化 3中方法都可以实现
// _set.assign(size,-1);
}
void Union(int x1,int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 != root2)
{
_set[root1] += _set[root2];
_set[root2] = root1;
}
}
size_t Count()// 合并后的个数
{
size_t count = 0;
for (size_t i = 0; i < _set.size(); i++)
{
if (_set[i] < 0)
count++;
}
return count;
}
private:
int FindRoot(int X)// 查找父结点
{
while (_set[x] >= 0)
x = _set[x];
return x;
}
private:
vector<int> _set;
};
此时，再来看我们开头提的问题，就会变得很简单了：
size_t friends(const int n,const int m,int r[][2])
{
UnionFind u(n + 1);//根据题目给出的编号，为方便解决题目，所以没有使用0号位置
for (int i = 0; i < m; i++)
u.Union(r[i][0],r[i][1]);
return u.Count() - 1;//因为0号位置没有使用，而初始化的-1为负数，所以要减1
}
int main()
{
const int m = 3;
const int n = 5;
int r[3][2] = { { 1,2 },{ 2,3 },{ 4,5 } };
cout << "朋友圈个数:" << friends(n,m,r) << endl;
return 0;
}
运行结果：
以上是大佬教程为你收集整理的【数据结构】并查集全部内容，希望文章能够帮你解决【数据结构】并查集所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。