第3讲——并查集

常见操作：

合并两个集合；

查找某个元素属于哪个集合；

方法一：

用最小元素标记所在集合

//查找 find1(x) { return set[x];//每个元素指向共同的老大； } //o(1); //合并 Merge1(a,b) { i=min(a,b); j=max(a,b); for(k=1;k<=N;k++)//遍历所有元素 { if（Set[k]==j) Set[k]=i; } } //o(n);

方法二：

每个集合用一颗有根树表示

//查找 find2(x) { r=x; while(Set[r]!=r) r=Set[r];//一直往上找，直到找到自己的老大； return r; } //最坏o(n); //合并 merge2(a,b) { set[a]=b; } //o(1);

避免最坏情况：

方法：将深度小的树合并到深度大的树；

//查找 find2(x) { r=x; while(set[r]!=r) r=set[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 r=x; while(bin[r]!=r) r=bin[r]; return r; } void merge(int x,int y) { int fx,fy; fx=findx(x); fy=findx(y); if(fx!=fy) bin[fx]=fy; } int main() { int n,m,i,x,y,cnt; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) bin[i]=i; for(scanf

经典应用：

最小生成树

如何求

（1）prime算法

（2）kruskal算法