什么是并查集
并查集处理两个问题：查询图中的两个节点是否在同一个顶点中，将两个不相交集合进行合并。
设计并查集的两种思想
1、quick-find，基于id
基于id的思想给每一个元素分配一个唯一的标识，称为id。如果两个元素的id一样，标识他们属于同一个集合。合并的时候，需要 其中一个集合中的所有元素的id赋值成为另一个集合的id。
优点：查询两个元素是否在一个集合中很快，时间复杂度O(1)。
缺点： 两个集合合并成一个集合较慢，需要遍历其中一个集合的所有元素。
2、quick-union：基于parent
基于parent的思想来自于记录每个顶点的父亲顶点是谁。这样设计“并查集”的思想也叫“代表元”法。不再使用id数组，而使用parent数组。parent数组的定义是：parent[i]表示第i个对象的父亲节点的索引。在该定义下，根节点的父亲节点是自己。
详解代表元法
代表元的三个不重要：1、根节点与非根节点只是位置不同，没有附加的含义；2、合并的时候任何一个集合的根节点指向另一个集合的根节点即可，树的形态不重要。
代表元法可能造成的问题:树的高度过高，查询性能降低。解决方案有：按秩合并，路径压缩
按秩合并
按秩合并的意思是：让树的秩较小的树的根节点指向树的秩较大的树的根节点。这里的秩有两种含义：按size合并，指让树的节点总数较小 根节点指向 节点总数较大的树的根节点，用于需要维护每个连通分量结点个数的时候；按rank合并指让树的高度较小的树的根节点指向树的高度较大的树的根节点，绝大多数时候适用。
路径压缩
路径压缩方式1：隔代压缩，指两部一跳，一直循环执行 当前节点指向它父亲节点的父亲节点 操作
路径压缩方式2：完全压缩，把从查询节点到根节点沿途经过的所有节点都指向根节点。
时间复杂度
同时使用按秩合并 路径压缩时，最坏情况的复杂度O(mα(n))，这里α(n) 是一个增长非常慢的函数，α(n)≤4。
并查集模板代码
class UnionFind {
public:
vector<int> parent;
vector<int> size;
int n;
public:
UnionFind(int _n): n(_n), parent(_n), size(_n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int findset(int x) {
return parent[x] == x ? x : parent[x] = findset(parent[x]);
}
bool unite(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
swap(x, y);
}
parent[y] = x;
size[x] += size[y];
return true;
}
bool connected(int x, int y) {
x = findset(x);
y = findset(y);
return x == y;
}
int count_root(){
int res = 0;
for (int i = 0; i < parent.size(); ++i) {
if(i == parent[i]){
res++;
}
}
return res;
}
};并查集相关问题