「数据结构」并查集

并查集($union-find\ \ set$)是一种可以__动态维护__若干个不重叠的__集合__，并支持__合并与查询__的数据结构，支持以下两种基本操作：

• $Find$，查询一个元素属于哪个集合(即查找根)
• $Union$，把两个集合合并成一个集合

基本实现

我们可以使用树形结构存储集合，树上每个点表示一个元素，树根可以代表这个集合

使用一个数组ufs[]来保存每个节点的父亲节点

则合并$x,y$所在的集合可以表示为$ufs[root_x]=root_y$

查找根节点可以一直沿着数组向上查找

路径压缩

防止整棵树的链非常长，导致每次查询时间复杂度极高，可以在__每次执行$Find$操作时，把访问的节点指向根节点__，这种方法称为__路径压缩__，$Find$操作的时间复杂度为$O(log_2n)$

$Code\ Below:$

int ufs[maxn];

//初始化，每个点独立(自己是自己的根)
for (int i = 1; i <= n; ++i) ufs[i] = i;

//Find操作
int find(int x) {
    return x == ufs[x] ? x : ufs[x] = find(ufs[x]);
}

//union操作(注意union是C++关键字)
void unionn(int x, int y) {
	ufs[get(x)] = get(y)
}

带权并查集

有时，需要维护的每个节点到根节点的边权值，可以增加一个数组d[]来保存权值，对于两个操作也有所更改

再增加一个数组size[]记录每个树根上集合大小

//Find
int find(int x) {
	if (ufs[x] == x) return x;
    int fx = find(ufs[x]);
    d[x] += d[ufs[x]];
    return ufs[x] = fx;
}

//union
void union(int x, int y) {
	int fx = find(x), fy = find(y);
    ufs[fx] = fy; d[fx] = size[fy];
    size[fy] += size[fx];
}

可撤销并查集

可能需要维护一个并查集并要求可以__撤销__两节点的连接关系

我们可以对每个操作$(u, v)$执行前，把节点$u$换为树根(不难发现，$ufs[]$变化的只有从$u$到原节点的一条链上)

然后对于操作

• $Connect\ u\ v$，需要把$u$的父亲节点设为$v$
• $Delete\ u\ v$，可以把$v$的父亲节点设为$0$
• $Query\ u\ v$，直接暴力搜索$v$所在的链即可

struct UnionFindSet {
    int ufs[maxn];
    void init() {
        for (int i = 0; i <= n; ++i) {
            ufs[i] = i;
        }
    }
    inline void sroot(int u) { //换u为根
        for (int i = 0, fa = ufs[u]; u; fa = ufs[u]) {
            ufs[u] = i; i = u; u = fa;
        }
    }
    void connect(int u, int v) {
        ufs[u] = v;
    }
    void deleteuv(int u, int v) {
        ufs[v] = 0;
    }
    void query(int u, int v) {
        for (; v != u && v; v = ufs[v]);
        puts(v == u ? "Yes" : "No");
    }
};

$Luogu$模板题目

Luogu P3367 并查集 (普通并查集)

Luogu P1196 银河英雄传说 (带权并查集)

Luogu P2147 洞穴勘探 (可撤销并查集)