并查集入门简单笔记

（简要笔记，仅供参考，可能存在瑕疵或者不正确的地方，望指正）

用一个点作为一个连通块的起源并且代表这个连通块，连通块的任何数都和这个起源相连；（连通块的点相互间都有联系）

并查集，可以将两个不同的连通块合并，形成一个大的连通块。

1，初始化

for(int i=1;i

{

fa[i]=i;

}

2,find函数//得到一个点的起源

int find(int x)

{

while(x!=fa[x])x=fa[x];

return x;

}

3,合并函数merge

void merge(int x,int y)//将x,y合并到一起，说明有关系

{

x=find(x);

y=find(y);

if(x!=y) //如果不是同一个起源，合并

fa[x]=y;//让两个数的起源 一样，fa[y]=x也可以；

return;

}

代码优化：

以上代码的find函数中,一个点需要循环多次向上寻找源头，可能会出现超时的情况，稍微调整一下find：

int find(int x1)

{

int x2=x1，pre;

while(x2!=fa[x2])x2=fa[x2];

while(x1!=fa[x1])

{

pre=x;

x=fa[x];

fa[pre]=x2;

}

return x2;

}

用递归写//比较方便

int find(int x)

{

return x==fa[x]?x:fa[x]=find(fa[x]);

}

用栈写

int find(int x){

stacksta;

while(x!=fa[x]){

sta.push(x);//如果x不是源头，把x压入栈中，寻找下一个；

x=fa[x];

}最终得到x的源头；

while(!sta.empty())//将栈中的点的源头一个一个变成最终源头x；

{

fa[sta.top()]=x;

sta.pop();

}

return x;

}