本篇博文旨在介绍一种数据结构——并查集；本文介绍了该数据结构的使用场景，并用代码进行了实现该数据结构

朋友圈问题：

1、已知，有n个人和m对好友关系(存于一个集合r中)

2、如果两个人是直接的或者间接的好友（好友的好友的好友。。。），那么他们属于一个集合，就是一个朋友圈里的

3、写出程序，求这n个人中一共有多少个朋友圈

文字描述还不明白的童鞋，可以看下面这个例子

例如：

n = 5 m = 3   

r = { { 1 , 2 },{ 2 , 3 },{ 4 , 5 } }

五个人有三对朋友关系

根据 集合r  我们可以看出1 、 2 、3 属于一个朋友圈，4和5属于一个朋友圈

所以结果有两个朋友圈

由于之前学习过哈希表

所以就想出了这样的解法

建立一个长度为n+1的数组（可以利用vector）

对应下标代表的是该人

然后遍历一遍 集合r  比如（1,2）就将2挂到1节点的后面

最后我们遍历一遍该数组，从1链接的节点中找到2，然后去找下标为2的数组链接的数字3，再找3，然后3没有链接节点，则表示是一个朋友圈

依次轮推，可以算出两个朋友圈

这个方法的确可行

但是，当关系量稍微复杂点就不好使了

其实7个人同属于一个朋友圈，但是1-2结束，就多算一个朋友圈

而且，由于处理不当还出现了循环的问题，比如1-2-3-1

当然，这种情况可以通过加以处理来避免

但是这样也太复杂了

有没有一种简便的方法来处理这个问题呢？

这里引入这次要介绍的数据结构——并查集

并查集

基本概念

将N个不同的元素分成互不相交的集合

然后按照规律将两个集合进行合并

基本思想

1、首先我们建立n个大小的数组，分别代表人的序号

将数组的所有值初始化为 -1 ，代表各自属于各自的集合

2、根据 集合r 对数组元素的值进行修改

比如 {0,6}

将a[0] 的值加上 a[6]的值

然后将a[6]所存的值改为 a[0]的下标 0 

修改后的下标如下图所示

下面，如果0和4产生了关系，{0,4}

那么找到4的根（为1），将a[1]的值加到a[0]上，然后将a[1]的值改为a[0]的下标0

通过对数组元素的遍历，只要值小于0，即代表为一个集合（朋友圈）中

代码实现

#PRagma once#include<iostream>using namespace std;#include<vector>//定义并查集class UnionFindSet{public:	//构造函数，将初始值置为-1	//并进行扩容	UnionFindSet(size_t n)	{		v.resize(n+1, -1);	}	//找到根节点	size_t FindRoot(size_t x)	{		size_t ret = x;		while (v[ret] >= 0)			ret = v[ret];		return ret;	}	//将两个人的朋友圈进行合并	void Union(size_t x1,size_t x2)	{		size_t root1 = FindRoot(x1);		size_t root2 = FindRoot(x2);		//同根，已经在一个集合		if (root1 == root2)			return;		v[root1] += v[root2];		v[root2] = root1;	}	//判断是否在一个集合	bool IsInSet(int x1, int x2)	{		return FindRoot(x1) == FindRoot(x2);	}	//求集合(朋友圈)的个数	size_t SetSize()	{		size_t count = 0;		for (size_t i = 0; i < v.size(); ++i)		{			if (v[i] < 0)				count++;		}		return count-1;	}protected:	vector<int> v;};void TestUnionFindSet(){	//五个人，四个人有朋友圈关系	const int n = 5;	const int m = 4;	UnionFindSet ufs(n);	int r[m][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 2, 4 } };	for (size_t i = 0; i < m; ++i)	{		ufs.Union(r[i][0], r[i][1]);	}	cout << "朋友圈的个数为:" << ufs.SetSize() << endl;}
代码的GitHub链接
https://github.com/haohaosong/DataStruct/blob/master/UnionFindSet.h