C/C++ 并查集及其优化笔记整理

个人笔记，仅供复习

1.1 集合运算：交、并、补、差，判断一个元素是否属于一个集合。

1.2 并查集：集合并、查某元素属于什么集合。

1.3 并查集问题中集合存储的实现：用树结构表示集合，树的每一个结点代表一个元素

2.对并查集的操作

2.1 查询：为了查询两个结点是否属于同一集合，我们需要沿着树向上走，来查询包含这个元素的树的根是谁。如果两个结点走到了同一个根，那么就可以知道它们属于同一组。

2.2 合并：从一个集合的根向另一个集合的根连边，这样两棵树就变成了一棵树，也就把两个集合并成一个集合了。

2.2.1 伪代码：（将X1和X2两个元素所在的集合合并）

• 分别找到到X1和X2两个元素所在集合树的根结点
• 如果它们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

3.优化

3.1 路径压缩（合并时的优化）：

• 对于每棵树，记录它的高度（Rank）
• 合并时，如果两棵树Rank不同，那么从Rank小的向Rank大的连边

3.2 路径压缩（查询时的优化）：对于每个结点，一点向上走到了一次根节点，就把这个点到父节点的边改为直接向根节点连边。

3.3 代码实例：

#include<iostream>
using namespace std;
const int maxn = 100;
int par[maxn];
int Rank[maxn];//优化

void clear(int n){//初始化n个元素 
        for(int i = 0;i < n;i++){
                par[i] = i;//一开始把每个节点看成一棵树
                Rank[i] = 0;
        }
}
int Find(int x){
        if(par[x] == x) return x;
        else par[x] = Find(par[x]);//优化
}
void unite(int x,int y){//将x和y所属集合合并 
        x = Find(x);
        y = Find(y);
        if(x == y)      return;
        if(Rank[x] < Rank[y])        par[x] = y; 
        else{
                par[y] = x;
                if(Rank[x] == Rank[y])  Rank[x]++;
        } 
}
bool same(int a,int b){//判断a和b是否属于同一集合 
        return Find(a) == Find(b);
}