问题提出：
有N个同学，他们之间有些是朋友，有些不是。"友谊"是可以传递的，例如A与B是朋 友，B与C是朋友，那么A与C也是朋友;朋友圈就是完成"友谊"传递后的一组朋友。 给定N*N的矩阵代表同学间是否是朋友，如果M[i][j] = 1代表第i个学生与第j个学生是朋 友，否则不是。求朋友圈的个数。
示意图
这个问题可以用并查集解决：
并查集(Union Find)，又称不相交集合(Disjiont Set)，它应用于N个元素的集合求并(union)与查询(find)问题，在该应用场景中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。虽然该问题并不复杂，但面对极大的数据量时，普通的数据结构往往无法解决，并查集就是解决该种问题最为优秀的算法。
示意图
并查集的实现方式有两种：数组实现和森林实现；
数组实现方式
![]()
数组实现方式
数组实现方式
从上面可以看出，find操作的时间复杂度为O(1)。而union操作时间复杂度为O(n)。对于海量数据而言，这样实现方式还不是最佳的。
并查集森林实现方式
使用森林存储集合之间的关系，属于同一集合的不同元素，都有一个相同的根节点 ，代表着这个集合。 当进行查找某元素属于哪个集合时，即遍历该元素到根节点，返回根节点所代表的集 合;在遍历过程中使用路径压缩的优化算法，使整体树的形状更加扁平，从而优化查 询的时间复杂度。 当进行合并时，即将两颗子树合为一颗树，将一颗子树的根节点指向另一颗子树的根 节点;在合并时可按子树的大小，将规模较小的子树合并到规模较大的子树上，从而使 树规模更加平衡，从而优化未来查询的时间复杂度。
示意图
class DisjoinSet
{
private:
std::vector<int> id;//用来存放该结点的父亲结点是哪一个
std::vector<int> size;//记录当前元素所在集合的大小
int count;//并查集里集合的数量，初始值为元素的个数
pubic:
DisjoinSet(int n)
{
for(int i=0;i<n;i++)
{
id.push_back(i);
size.push_back(1);
}
count = n;
}
};
路径压缩优化是并查集最简单、也是非常有效的一个优化。
在执行find(a)的过程中，路径压缩优化会将从a到d路径上的所有点都指向有根树的根，也就是d。这么做的好处在于：通过这样的处理，能将有根树的高度尽可能降低，下次再进行查询或合并操作的时候时间开销就更小了。路径压缩优化实现起来并不复杂，在find函数中，当发现当前结点不是根结点时，会不断的递归求解，并将结果直接作为返回值返回了。
示意图
int find(int p)
{
while(id[p]!=p)
{
id[p]=id[id[p]];//路径压缩，把该点父节点设定为父节点的父节点
p=id[p];
}
return p;
}
合并
void unionMen(int p,int q)
{
int p_p = find(p);
int q_p = find(q);
if(p_p==q_p)return;
if(p_p!=q_p)
{
if(size[q_p]<size[p_p])
{
id[q_p]=p_p;
size[p_p]+=size[q_p];
}
else
{
id[p_p]=q_p;
size[q_p]+=size[p_p];
}
count--;
}
}
完整代码可以戳➡️我的GitHub;
希望大家一起进步～
