0x15 并查集

[toc]

1. 啥是并查集

并查集(disjoint sets直译为不交集)，其实就是其英文名字的意思，若干个无交集的集合。对于其的操作就是中文名字所述，合并两个集合，查询某个元素属于哪一个集合。

2. 如何实现

2.1. 朴素实现

最直接的办法就是建立一个一维数组，数组中每个元素代表每个元素属于哪个集合。如dsjset[i]=3，就代表i号元素属于n号集合。这样对于查询操作来说时间复杂度是O(1)的，但是合并就很蛋疼，时间复杂度为O(n)。为了减少每次合并都要动集合内全部的元素，我们可以选择一个集合内部的代表元素，如i号元素，将所有与i号元素同集合的元素都指向它，dsjset[j]=i，而i号元素指向自己。这样当集合合并时，只需要改变i号元素的指向值，无须改变牵一发而动全身。其次我们并不关心某个元素属于哪一号集合，这个几号集合是无意义的，我们只关心它和谁在一个集合，和谁不在一个集合。因此选出一个代表元素是完全OK的。

但是这样的话随着集合的多次合并，想要查询就变得困难。如果有m次合并，那么查询集合的时间复杂度为O(m)。

const int N = 1e5 + 10;
int dsj_sets[N], idx;

// 初始化，每个元素都属于一个单独的集合
void init(const int n) {
    for (int i = 1; i <= n; i++) {
        dsj_sets[i] = i;
    }
}

// 查询某个元素属于哪个集合
int get_parent(int elem) {
    if (dsj_set[elem] == elem) {
        // 集合代表
        return elem;
    }
    int parent = dsj_set[elem];
    return get_parent(parent);
}

// 合并两个元素所在的集合
void merge_sets(int elem1, int elem2) {
    int set1 = get_parent(elem1), set2 = get_parent(elem2);
    // 无须特判，如果set1=set2，那么数组中存储的还是它自身
    dsj_set[set1] = set2;
}

// 查询两个元素是否在同一集合
bool query(int elem1, int elem2) {
    return get_parent(elem1) == get_parent(elem2);
}

2.2. 路径压缩优化

虽然查询的时间复杂度变高，但是我们可以对其进行路径压缩优化。所谓路径压缩优化，就是在每次查询后，利用查询的信息，让之后再查询时不会走同样的弯路。

设想上面这种情况，在多次集合合并后，对于1、3、2元素来说，数组中存储的都不是其真正的集合父节点，需要查询多次才能找到真正的父节点，即5。但是一旦查询过一次，我们知道其真正的父节点后，就应该更新父节点信息，这样下次查询时就还是O(1)的。如对于1号元素来说，它本来存的是3，但是查询过一次后发现是5，那么它就应更新为5。其次对于4来说，它需要查多次才能到真正的父节点，那么它在一路上碰到的所有祖先节点也应当指向最新的根节点，即4查到父节点为5时，它查询路上碰到的3也应该一并更新。

对于路径压缩优化只需要改变get_parent函数：

int get_parent(int elem) {
    if (dsj_sets[elem] == elem) {
        return elem;
    }
    int dated_parent = dsj_sets[elem];
    int parent = get_parent(dated_parent);
    dsj_sets[elem] = parent;
    return parent;
}

最终查询的时间复杂度均摊应该是O(1)的，我也不知道咋算。

3. 并查集的应用

3.1. 合并查询集合

都叫并查集了，肯定可以用于合并、查询多个无交集的集合。这种问题比较直接，直接用就行。

3.2. 无向图节点连通性

并查集还可以维护一张无向图的节点连通性。可以想象，对于无向图中，每个点都相当于一个元素，如果两个点连通，那么可以认为它们同处一个集合。如果让两个点进行连通，那么两个点原本连通的点也会连通，这就相当于合并了两个集合。

不过并查集并不能快速的分离集合，所以只适用于无断开连通的无向图。再归纳一下，其实并查集解决了元素间的关系传递性。对于无向图，点与点一旦连通，那么就会将这个连通关系传递到原本和它们连通的点。不过这种关系传递性一旦传递，就很难断开关系。

最后更新: February 13, 2023