常见两种操作:
第一种方法:
合并两个集合(代码效率不高)
/
merge1(a,b) { i=min(a,b); j=max(a,b); for(i=0;i<=N;i++) { if(set[k]==j) { set[k]=i; } } }
对数组的所有元素进行遍历一边,查找数组元素是否为6,若是6,则将数组元素改写为2
查找某元素属于哪个集合
findl(x) { return set[x]; }
第二种方法:(树)
合并两个集合
直接将领导a归附于领导b即可
merge2(a,b) { set[a]=b; }
/
查找某元素属于哪个集合(效率不高)
find2(x) { r=x; while(set[r]!=r) { r=set[r]; return r; } }
/
优化后的算法:
查找:
解释:每个集合中最小的为树的根,每个节点的父节点是领导(不是最高领导,只是直属领导)
/
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; } }
解释:树高的做领导,方框格格里面的(数组元素)用于装着领导