并查集
2018-04-26 本文已影响0人
laochonger
部分来自：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
