查集讲解(按秩合并与路径压缩)

自看。。。

借鉴自:https://blog.csdn.net/u011056504/article/details/51222494

1、路径压缩

void find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

2、按秩合并

给每个点一个秩,其实就是树高 
每次合并的时候都用秩小的指向秩大的,可以保证树高最高为log2(n)log2(n) 
操作的时候,一开始所有点的秩都为1 
在一次合并后,假设是点x和点y,x的秩小 
当然x和y都是原来x和y所在区间的顶点 
设点x秩为rank[x] 
将fa[x]指向y,然后将rank[y]的与rank[x+1]取max 
因为rank[x]为区间x的高,将它连向y之后,y的树高就会是x的树高+1,当然也可能y在另一边树高更高,所以取max

程序

同样,fa[x]为x的父亲,就是x指向的点,rank[x]为点x的秩

//查询:
void find(int x)
{
    return f[x] == x ? x : find(f[x]);
}

//修改:
    
    int r = find(x);
    int l = find(y);
    if(r == l) continue;
    if(rank[l] <= rank[r]) f[l] = r, rank[r] = max(rank[r], rank[l] + 1);
    else f[r] = l, rank[l] = max(rank[l], rank[r] + 1);
自己选择的路,跪着也要走完。朋友们,虽然这个世界日益浮躁起来,只要能够为了当时纯粹的梦想和感动坚持努力下去,不管其它人怎么样,我们也能够保持自己的本色走下去。
原文地址:https://www.cnblogs.com/WTSRUVF/p/9416217.html