并查集

部分来自：https://blog.csdn.net/The_best_man/article/details/62418823

性质

并查集算法（union_find sets）不支持分割一个集合,求连通子图、求最小生成树

用法

并查集是由一个数组pre[]，和两个函数构成的，一个函数为find()函数，用于寻找前导点的，第二个函数是join()用于合并路线的

int find(int x)
{
   return pre[x]==x?x:pre[x] = find(pre[x]);//找到根结点并压缩路径
}

路径压缩为了加快查找的速度，将x点与其根节点直接相连，构造成类似于只有叶子结点而没有分支结点的树

---

join()函数

void join(int x,int y)
{
    int a=find(x);//x的根节点为a
    int b=find(y);//y的根节点为b
    if(a!=b)//如果a,b不是相同的根节点，则说明ab不是连通的
    {
        pre[a]=b;//我们将ab相连 将a的前导结点设置为b
    }
}

---

初始化

我们将每一个结点的前导结点设置为自己，如果在join函数时未能形成连通，将独立成点

for(int i=0;i<n;i++)//n表示输入的结点的个数
{
    pre[i]=i;//将每一个结点的前导点设置为自己

}

image image image image image image image image image

并查集的应用实例

亲戚

犯罪团伙

食物链

无所不在的宗教

改写kruscal算法