早上一番捣鼓,把以前丢失的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; }
原文：http://www.cnblogs.com/hhbeast/p/6978120.html