并查集

模板

字数统计: 317阅读时长: 1 min

 2021/04/23   Share

并查集

并查集简介

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

实现并查集

路径压缩

//初始化，每个人都是自己的爹
void init(int n) {
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
    }
}
//查询（路径压缩）
int find(int t) {
    return fa[t] == t ? t : fa[t] = find(fa[t]);
}
//合并
void merge(int i, int j) {
    fa[find(i)] = find(j);
}

按秩合并

//初始化
void init(int n) {
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
        ranks[i] = 1;
    }
}
//查询
int find(int t) {
    return fa[t] == t ? t : find(fa[t]);
}
//合并
void merge(int i, int j) {
    int x = find(i);
    int y = find(j);
    //把简单的树往复杂的树上合并
    //把ranks小的树往ranks大的的树上合并
    if (ranks[x] <= ranks[y]) {
        fa[x] = y;
    }
    else {
        fa[y] = x;
    }
    if (ranks[x] == ranks[y] && x != y) {
        ranks[y]++;
    }
}