第3讲——并查集

常见操作合并两个集合查找某个元素属于哪个集合方法一用最小元素标记所在集合//查找 find1(x) { return set[x];//每个元素指向共同的老大 } //o(1); //合并 Merge1(a,b) { imin(a,b); jmax(a,b); for(k1;kN;k)//遍历所有元素 { ifSet[k]j) Set[k]i; } } //o(n);方法二每个集合用一颗有根树表示//查找 find2(x) { rx; while(Set[r]!r) rSet[r];//一直往上找直到找到自己的老大 return r; } //最坏o(n); //合并 merge2(a,b) { set[a]b; } //o(1);避免最坏情况方法将深度小的树合并到深度大的树//查找 find2(x) { rx; while(set[r]!r) rset[r]; return r; } //合并 merge3(a,b) { if(height(a)height(b)){ height(a)height(a)1; set[b]a;} else if(height(a)height(b)) set[a]b; else set[b]a; }方法三带路径压缩的查找find3(x) { if(set[x]!x) set[x]find3(set[x]); return set[x]; }例题#include stdio.h int bin[1002]; int findx(int x) { int rx; while(bin[r]!r) rbin[r]; return r; } void merge(int x,int y) { int fx,fy; fxfindx(x); fyfindx(y); if(fx!fy) bin[fx]fy; } int main() { int n,m,i,x,y,cnt; while(scanf(%d,n),n) { for(i1;in;i) bin[i]i; for(scanf经典应用最小生成树如何求1prime算法2kruskal算法