首页 > 代码库 > 并查集--连通图相关
并查集--连通图相关
早上一番捣鼓,把以前丢失的onenote笔记找出来一部分.
看到并查集,大二做的笔记,现在已经毫无印象了
记得当时看的时候挺费劲,云里雾里的
现在再看一遍竟然毫无压力,一次读懂
其实确实挺简单的,没有那么高深.可能当时玩acm的时候太没自信了,看啥都难...
核心思想是用一个节点代表一块连通分支
可以通过路径压缩来减少以后查找的时间
非路径压缩递归写法:
int fFind(int i) { if(pre[i]!=i) pre[i]=fFind(pre[i]); return pre[i]; }
路径压缩非递归写法:
int fFind(int i) { int roooot=i; while(pre[roooot]!=roooot) roooot=pre[roooot];//寻根 int tmp; while(pre[i]!=roooot) { tmp=pre[i]; pre[i]=roooot; i=tmp; }//路径压缩 return pre[i]; }
适用于代码行数强迫症的一行写法:
int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
两个相关并查集交融的mix函数:
mix函数 void mix(int a,int b) { int i=fFind(a),j=fFind(b); if(i!=j) pre[i]=j; }
并查集--连通图相关
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。