定义
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
应用
若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个朋友关系图，求任意给出的两个人是否在一个朋友圈。 规定：x和y是朋友，y和z是朋友，那么x和z在一个朋友圈。如果x,y是朋友，那么x的朋友都与y的在一个朋友圈，y的朋友也都与x在一个朋友圈。
如下图：
代码：
//找朋友圈个数
//找父亲节点
int FindRoot(int child1, int *_set)
{
int root = child1;
while (_set[root] >= 0)
{
root = _set[root];
}
return root;
}
//合并
void Union(int root1, int root2, int *&_set)
{
_set[root1] += _set[root2];
_set[root2] = root1;
}
int Friend(int n, int m, int r[][2])//n为人数，m为组数，r为关系
{
assert(n > 0);
assert(m > 0);
assert(r);
int *_set = new int[n];
for (int i = 0; i < n+1; i++)
{
_set[i] = -1;
}
for (int i = 0; i < m; i++)
{
int root1 = FindRoot(r[i][0],_set);
int root2 = FindRoot(r[i][1],_set);
if ((_set[root1] == -1 && _set[root2] == -1) || root1 != root2)
{
Union(root1, root2, _set);
}
}
int count = 0;
for (int i = 1; i <= n; i++)
{
if (_set[i] < 0)
{
count++;
}
}
return count;
}
//主函数
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
#include
#include"UnionFindSet.h"
int main()
{
int r[][2] = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 } };
cout << Friend(6, 4, r) << endl;
system("pause");
return 0;
} 另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
