并查集

简介

英文：Disjoint Set，即“不相交集合”。将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：

1. 合并两个集合；
2. 查找某元素属于哪个集合。

代码

1 无优化

const int maxn = 1e5;
int node[maxn];//每个节点的父节点

//初始化
void init(int n) {
    for( int i=0; i<=n; i++ ){
        node[i] = i;
    }
}
//查找当前元素所在树的根节点(代表元素)
int find(int x) {
    if (x == node[x])
        return x;
    return find(node[x]);
}
//合并x和y所在的集合
void merge(int x, int y) {
    int root_x = find(x);//找到根节点
    int root_y = find(y);
    if (root_x == root_y)//两者根节点相同
        return ;
    node[root_x] = root_y;//将x的根节点与y的根节点相连
}
//判断xy是否属于一个集合
bool same(int x, int y) {
    return find(x) == find(y);
}

2 优化(路径压缩+按秩合并)

const int maxn = 1e5;
int node[maxn];//每个节点的父节点
int Rank[maxn];//树的高度

//初始化
void init(int n) {
    for (int i=0; i<=n; i++) {
        node[i] = i;
        Rank[i] = 1;
    }
}
//路径压缩
//查找当前元素所在树的根节点(代表元素)
int find(int x) {
    if (x == node[x])
        return x;
    return node[x] = find(node[x]);//在第一次查找时，将节点直连到根节点
}
//按秩合并
//合并x和y所在的集合
void merge(int x, int y) {
    int root_x = find(x);//找到根节点
    int root_y = find(y);
    if (root_x == root_y)//两者根节点相同
        return ;
    //判断两棵树的高度，然后在决定谁为子树
    if (Rank[root_x] < Rank[root_y])
        node[root_x] = root_y;//将x的根节点接到y的根节点下
    else {
        node[root_y] = root_x;//将y的根节点与x的根节点下
        if (Rank[root_x] == Rank[root_y])//树的高度相同
            Rank[root_x]++;//root_x树高度+1
    }
}
//判断xy是否属于一个集合
bool same(int x, int y) {
    return find(x) == find(y);
}

时间复杂度

直接实现的话，时间复杂度最坏可以到O(n)。 两个常见优化，启发式合并，路径压缩。

• 启发式合并：把大小较小的集合挂在较大的集合上。（有的写法是考虑深度而不是大小）
• 路径压缩：询问过的点到根节点的路径，都直接挂在根节点上。

实现其中任意一个时间复杂度变为O(\log n)。 实现其中两个，时间复杂度变为O(\alpha(n))，其中\alpha(n)是阿克曼函数的反函数，可以认为非常小。

多数情况下为了简单，都实现路径压缩（只需要一句赋值）而不实现启发式合并（需要记录大小）

在某些题目中由于会爆栈，需要使用非递归的find函数。

练习

1. 洛谷——P3367 【模板】并查集