并查集(防退化)

防退化的关键操作在于,记录每一个点的高度,合并的时候,将高度较小的点并到高度较大的点上去。

同时还有一个优化技巧就是路径压缩,它会改变树的高度,但是为了方便起见,也不修改 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]++;
    }
}