防退化的关键操作在于,记录每一个点的高度,合并的时候,将高度较小的点并到高度较大的点上去。 同时还有一个优化技巧就是路径压缩,它会改变树的高度,但是为了方便起见,也不修改 high 的值
防退化的关键操作在于,记录每一个点的高度,合并的时候,将高度较小的点并到高度较大的点上去。
同时还有一个优化技巧就是路径压缩,它会改变树的高度,但是为了方便起见,也不修改 high 的值
合并操作:
x=find(x),y=find(y); if(x!=y) { if(high[x]<high[y]) f[x]=y; else{ f[y]=x; if(high[x]==high[y]) high[x]++; } }