并查集

并查集是一种用来管理元素分组情况的数据结构。不过需要注意的是并查集虽然可以进行合并操作，但是却无法进行分割操作。并查集可以高效地进行如下操作：

1. 查询元素a和元素b是否属于同一组。
2. 合并元素a和元素b所在的组。

算法：

用集合中的某个元素来代表这个集合，该元素称为集合的代表元。

一个集合内所有元素组织成以代表元为根的树形结构。

对于每一个元素par[ x ]指向x在树形结构上的父亲节点。如果x是根节点，则令par[ x ] = x。

对于查找操作，假设需要确定 x 所在的集合，也就是集合的代表元。可以沿着par[ x ]不断在树形结构中向上移动，直到到达根节点。

判断两个元素是否属于同一集合，只需要看他们的代表元是否相同即可。

路径压缩：

为了加快查找速度，查找时将 x 到根节点路径上的所有点的parent设为根节点，该方法称为压缩路径。

使用该优化后，平均复杂度可视为Ackerman函数的反函数，实际应用中可粗略认为是一个常数。

用途：

1. 维护无向图的连通性。支持判断两个点是否在同一连通块内，和判断增加一条边是否会产生环。
2. 用在求解最小生成树的Kruskal算法里。

并查集的实现：

const int N = MAX_INT;
int par[N];
int rank[N]; 

//并查集初始化 
void init(int n) {
    for(int i = 0; i < n; ++i) {
        par[i] = i;
        rank[i] = 0;
    }
}

//查找 
int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

//合并 
void unite(int x, int y) {
    //找到 x 和 y 的根节点 
    x = find(x);
    y = find(y);

    if(x == y) return;
    //如果 x 的深度小于 y ，则 x 并入 y 集合，即将 x 的父节点设为 y  
    if(rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        //如果 x 的深度与 y 一样，则 x 需要加深一层。 
        if(rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

//判断 x 和 y 是否属于同一个集合 
bool same(int x, int y) {
    return find(x) == find(y);
}