(简要笔记,仅供参考,可能存在瑕疵或者不正确的地方,望指正)
用一个点作为一个连通块的起源并且代表这个连通块,连通块的任何数都和这个起源相连;(连通块的点相互间都有联系)
并查集,可以将两个不同的连通块合并,形成一个大的连通块。
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){ stack 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; } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)