标签：val int fy 查集 fx 数据结构 find

并查集

---

简介

并查集是可以维护 元素集合 的数据结构。并查集通过把一个集合作为一棵树的方式，维护一个 森林（这暗含并查集可以维护连通块个数，如在 kruskal 中，通过并查集维护连通块个数就能快速判断循环退出条件），并使用树的 根节点代表各集合。这样一棵树的节点就对应该集合中的元素。可以方便地支持元素（合）并查（询）操作，我们会维护每个点指向的父亲节点。当然，根节点只能指向自己了。

有带权并查集、扩展域并查集、可撤销并查集和可持久化并查集等变体。

普通并查集

结构

维护一个数组记录父亲，并在初始化时指向自己。

int fa[N];

操作

查询

询问元素所在集合的根节点，通过递归不断上跳至父亲节点实现。不难发现当出现自环时我们就抵达了顶点，可以返回。

int find(int x) {return fa[x] == x ? x : find(fa[x]);}

合并

既然直接维护的是集合从属关系，要合并两个集合时直接将一棵树的根的父亲设为另一棵树的根节点即可。

void unite(int x, int y) {fa[find(x)] = find(y);}

并查集优化

使用最为广泛的是并查集的路径压缩技巧。大多数时候我们使用并查集并不关心元素间 严格的父子关系，只是想知道它们是否属于同一集合，此时普通并查集的时间复杂度就不可观了。想象一下，从一条链的底端爬到顶端后才能返回代表这一集合的元素，实在是太过耗时了。而一朵美妙的菊花图才是效率之王！针对查询的优化——路径压缩由此而来：把一条链的路径压成一条“直通边”岂不美哉？

注意：不难看出，在需要判定加入顺序等关心严格父子关系的情景时，路径压缩会致错。如：[可撤销并查集](P5787 二分图 /【模板】线段树分治 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))。同样，在节点维护了与路径有关信息时（如树高），路径压缩同样不能完全兼容，所以才有了按秩合并，详见知乎讨论。

结构

我们完全可以改变此时并查集记录的信息：在加入时记录其父节点，而后对每个节点 在可能时 尽快更新成记录其所在集合的根节点，那么之后的查询我们就可以快速得到答案，省去一次次“爬楼”的过程了。

int rt[N];

操作

路径压缩

前文说到要尽可能更新，那么在查询时就 一路更新 节点信息自然是不二之选——反正这次经过的链上所有的点都可以，也需要更新，那一并维护即可。在代码层面，具体地，在递归后将返回值顺道更新为当前节点指向的根节点。

int find(int x) {return rt[x] == x ? rt[x] = find(rt[x]);}
//不压行的，
int find(int x) {
    if (x == rt[x]) return x;
    rt[x] = find(rt[x]);
    return rt[x];
}

启发式合并

合并操作也有其优化方法：启发式合并、按秩合并。启发式合并是一种常见的优化，对合并过程人为干涉，符合直觉地，一般将大小更小的并入更大的集合，这样未来查询时需要更新rt[]数组的节点自然更少。同理，也有按深度（树高）较矮的并入更高的集合。但是我们前面提到，使用路径压缩时会改变树高，故根节点存储的高度信息干脆不进行更新，直接使用这个称为“秩”的近似值进行求并优化。事实证明这样也能提升效率。

void unite(int x, int y) { //按大小合并
     x = find(x), y = find(y);
     if (x == y) return;
     if (sz[x] < sz[y]) swap(x, y);
     rt[y] = x; sz[x] += sz[y];
 }
void unite(int x, int y) { //按秩合并
	x = find(x); y = find(y);
    if (x == y) continue;
    if (dep[x] < dep[y]) swap(x, y);
    rt[y] = x; dep[x] += (dep[x] == dep[y]);
}

trick——关于合并的思考：我们都知道并查集支持的是合并而非删除操作，而当只有删边和询问时我们有个经典的处理方式：时光逆流，从而将删边改为加边。

带权并查集

有时候，我们需要维护 类似前缀和 的值，即加入点时给出其与父亲之间的 相对关系（通常可以转化成 边权），并实时维护从根节点到此节点的（异或）和等可以使用前缀和得到的相对信息。于是我们想要知道任意两个同集合的点之间的绝对关系就可以通过从根到这两点的相对信息得到。举个简单例子：每个人都有成绩，每次给出两个人的成绩之差。比如有关系 \(a-b=x、b-c=y、b-d=z\) ，那么可以将 \(a\) 作为根，维护其他人与他成绩的差值 \(val(b)=-x、val(c)=-x-y、val(d)=-x-z\)。通过 \(val(d)-val(c)\) 就能逆向得到 \(d\) 比 \(c\) 多 \(y-z\) 分。

这在普通并查集中不难理解和实现，收集树上根节点到此点的链的信息即可。

结构

int rt[N], val[N];

操作

以普通并查集合并时维护位次为例。

int find(int x) {
	if (fa[x] == x) return x;
	int rt = find(fa[x]);
	rnk[x] += rnk[fa[x]];
	return rt;
}
void united(int x, int y) {
	int fx = find(x), fy = find(y);
	rnk[fx] += sz[fy];
	fa[fx] = fy;
	sz[fy] += sz[fx];
	sz[fx] = 0;
}

那么路径压缩可否用于这种带权并查集呢？在路径压缩后或许感觉混乱无比，是不是直接接到根节点就会略过路径的其他边？其实我们剖析一下路径压缩的过程：在 find() 函数中一定是 先一路递归更新了父亲节点到根节点 的信息，并将其接在根上后 再更新自身到父节点 信息，与正常 Dfs 顺序无异。所以我们依然可以直接在父亲节点的基础上加上本点影响。不过注意，一定是在 进入递归前 就记录下父亲节点编号，不然赋过新值后通过 rt[] 找到的就是根节点了。以维护路径点权和或维护异或和为例：

int find(int x) {
    if (x == rt[x]) return x;
    int fa = rt[x];
    rt[x] = find(rt[x]);
    val[x] ^= val[fa]; || val[x] += val[fa];
    return rt[x];
}

合并时，我们遇到了棘手的问题：比如合并 \(x、y\) 所在集合时给出的条件是使 real[x] = real[y] + w （因为带权并查集内部维护的是相对信息，为了便于区分，这里使用"real"表示真实值），但我们合并时是将 \(x\) 的根 fx=find(x) 接到 \(y\) 的根 fy=find(y) 上。因此我们需要求出一个合适的新值（\(fx\) 相对 \(fy\) 的值）赋给 \(val(fx)\)，以满足 \(fx\) 原本集合内各元素相对值仍不变，且更新原 \(fx\) 集合内元素的 \(val_{\to fx}\) 值为与 \(fy\) 的相对值 \(val_{\to fy}\) 后， \(val_{\to fy}(x)\) 与 \(val_{\to fy}(y)\) 做差能得到 \(w\)。 因为 find() 后分别得到了 \(x、y\) 与 \(fx、fy\) 的相对值 \(val_{\to fx}(x)、val_{\to fy}(y)\)。那么我们得到：

\[w=val_{\to fy}(x)-val_{\to fy}(y)=val_{\to fx}(x)+val_{\to fy}(fx)-val_{\to fy}(y) \\ \implies val_{\to fy}(fx)=val_{\to fy}(y)+w-val_{\to fx}(x) \]

所以使用解出的这个值，在之后更新原 \(fx\) 集合内元素的 \(val()\) 时就能满足条件。

void unite(int x, int y, int w) {
    int fx = find(x), fy = find(y);
    if (fx == fy) continue;
    rt[fx] = fy;
    val[fx] = val[y] + w - val[x];
}

直观地，将相对值反应成距离，find()后我们可以得到：

\(x\) 经由两条路径都到达了 \(fy\)，因此两条路径长度也应相等，尽管我们只会保留绿 \(\to\) 红而非蓝 \(\to\) 绿一线，但也能验证上面等式的成立。

扩展域并查集

结构

扩展域并查集使用了与 \(2-SAT\) 类似的建反集思想。这时依然维护每个元素所属集合，但现在的集合之间有阵营之分，可能两个集合毫无关系，也可能互为敌人，集合内部则一定同为朋友。而所谓“反集”，就是假想出一个与元素 \(x\) “作对” 的影子 \(x^{'}\)，这在处理敌人关系时可以方便地将敌对阵营都与 \(x^{'}\) 连接，使得 \(x^{'}\) 会联合一切 \(x\) 的敌人阵营，整合形成一个连通块，整个图就近似二分图了。实现时使用 \(x+n\) 可以方便地表示 \(x^{'}\)。

trick：合并时应注意顺序，一般只选择真实的元素（\(1\sim n\)）作为集合代表（树的根）方便统计。

比如题目给出的是 \(x、y,y、z\) 互为敌人，那么 \(x、z\) 就会被 \(y^{'}\) 拉拢，形成同一阵营，实现快速整合连通块。

int rt[N*2];

操作

扩展域并查集合并时秉持的原则就是：1.朋友的朋友还是朋友；2.敌人的敌人就是朋友。当然，有些时候也会要求朋友的敌人也是敌人，特别注意题目要求。

对于两个朋友关系的 \(a、b\)，将他们的阵营直接合并就行，unite(a,b)。而对于两个敌人关系的 \(a、b\)，他们的反集 \(a^{'}、b^{'}\) 阵营会分别拉拢 \(b、a\)，所以要 unite(a+n, b)、unite(b+n,a) 。朋友关系时用不用 unite(a+n,b+n) 取决于说没说朋友的敌人也是敌人。如果两者毫无瓜葛，这样合并了就相当于无故对其他人宣战，额外树敌使两者敌人联合只是减少了阵营数。

譬如上例中我们加入了 \(w、z\) 的友好关系，是否意味着 \(z\) 要对 \(w^{'}\) 保持敌对关系？不一定，题目没有允许朋友的敌人也是敌人时，同一阵营（绿）的不同元素（\(z、w\)）有各自的敌人阵营（橙、蓝）也是合法的。

比如在团伙一题中，[不允许这种情况出现](关于种族并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))，但在食物链中，因为种族概念的影响，同一种族有着共同的天敌，就一定需要合并敌人。又比如程序自动分析中，给出的条件只有相等或不等，但仅靠这种关系， \(x\ne y,x\ne z\Longrightarrow y=z\) 显然不成立，也就是说不能简单地认为“敌人的敌人是朋友”就将他们归为一类。此时只有等式满足传递性，即“朋友的朋友是朋友”生效，故而应该将所有等式条件处理后再判断不等条件是否满足。

可撤销并查集

前文我们才说过并查集仅支持合并，怎么现在就可以撤销了？其实，已经一再强调：路径压缩会破坏原有父子关系，无法复原加入顺序，但普通并查集记录的是原来加入时的父亲，通过记录一个栈维护新加入集合的那个（原）根节点，我们可以方便地在退栈时将它的父亲重定向回自己，实现两个集合的分离。此时失去了路径压缩优化，就一定注意使用按秩合并保证复杂度（毕竟也好不容易完全兼容一次）。经典的使用场景是配合线段树分治判定二分图。

结构

因为会用到按秩合并，所以需要记录加入这棵子树后树高的改变值，stk要开一个pair。

stack<pair<int, int> > stk[N];
int fa[N], h[N];

操作

查询

int find(int x) {return x == fa[x] ? x : find(fa[x]);}

合并

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (dep[x] < dep[y]) swap(x, y);
    stk.push({y, (dep[x] == dep[y])});
    fa[y] = x; dep[x] += (dep[x] == dep[y]);
}

撤销

在进行加入操作前记录要回退到的位置，在合并并操作完后回溯。回溯途中记得撤回加入时对父节点集合的树高贡献。

void work() {
    int tmp = stk.size();
    /*  unite(...)   */
    while (stk.size() > tmp) {
        int x = stk.top().first, derta = stk.top().second;
        dep[fa[x]] -= derta; fa[x] = x; stk.pop();
    }
}

可持久化并查集

通过主席树可以实现可持久化并查集，先挖坑。

标签：val,int,fy,查集,fx,数据结构,find
From： https://www.cnblogs.com/Arson1st/p/17795806.html