并查集

简介

并查集是为了解决图联通的问题而发明的算法，它可以实现$O(1)$时间复杂度的插入和平均$O(log(n))$时间的查询，从而快速处理判断两个元素是否属于同一个部分

并查集支持的操作

  • 寻找根节点(find)
  • 判断任意两个节点是否联通(is_connected)
  • 将两个节点合并(join)
  • 返回一个节点的联通个数(count)

并查集的实现

find

无路径压缩版本

1
2
3
4
5
6
7
int find(int x) {
    if(parent[x] == x) {
        return x;
    } else {
        return find(parent[x]);
    }
}

有路径压缩版本

1
2
3
4
5
6
7
8
9
int find(int x) {
    if(parent[x] == x) {
        return x;
    } else {
        int p = find(parent[x]);
        parent[x] = p;
        return p;
    }
}

is_connected

1
2
3
4
bool is_connected(int src, int dst) {
    if(find(src) == find(dst)) return true;
    else return false;
}

join

1
2
3
4
5
6
7
8
9
10
11
12
void join(int src, int dst) {
    int p_src = find(src);
    int p_dst = find(dst);
    if(p_src == p_dst) return;
    if(cnt[p_src] <= cnt[p_dst]) {
        cnt[p_dst] += cnt[p_src];
        parent[p_src] = p_dst;
    } else {
        cnt[p_src] += cnt[p_dst];
        parent[p_dst] = p_src;
    }
}

count

1
2
3
int count(int x) {
    return cnt[find(x)];
}

优化思路

路径压缩

  1. 找到该节点的根节点
  2. 将路径上的每个节点的父节点都指向根节点

优化合并

将较小的一棵树合并到较大的那棵树上