带权并查集和扩展域并查集的一些整理和理解（上）

请读者在有一定并查集基础上再阅读（至少要知道什么是带权和扩展域并查集）

在最近做题时候，我遇到了一些带权并查集和扩展域并查集的题目。我觉得它们都很难写也很难想，尤其是带权并查集我几乎第一时间无法想到是怎么做的，于是我打算把它们整理起来，上集只有带权并查集，下集只有扩展域并查集。

先来一道简单题

引入（并非带权或扩展域并查集题目）

837. 连通块中点的数量 - AcWing题库https://www.acwing.com/problem/content/839/这道题目并没有用到find函数里做额外数据的操作，但是在一些情况下仍然进行了额外数据的操作，比如要合并两个集合，那就要先进行寻找祖先节点，然后再进行把即将要被合并掉的祖先节点上的该并查集个数加到即将要合并进的并查集里，因为并查集的节点个数都存放在祖先节点里，所以要进行祖先节点寻找。但是这道题理论上来看并不是带权并查集题，因为带权并查集每个节点需要维护与根节点的距离或者相对关系，这道题只是为了”开胃“的。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], s[N];
int find(int x){if (x != p[x]) p[x] = find(p[x]);return p[x];
}
int main(){cin >> n >> m;for (int i = 1; i <= n; ++ i){p[i] = i; s[i] = 1;}while (m -- ){string s1; cin >> s1;int x, y;if (s1 == "C"){cin >> x >> y;if (find(x) == find(y)) continue;s[find(y)] += s[find(x)];p[find(x)] = find(y);}else if (s1 == "Q1"){cin >> x >> y;if (find(x) == find(y)) cout << "Yes" << endl;else cout << "No" << endl;}else {cin >> x;cout << s[find(x)] << endl;}}return 0;
}

正式的：

第一道带权并查集

240. 食物链 - AcWing题库https://www.acwing.com/problem/content/242/这道题就是经典的带权并查集问题，题目要求求出有多少个假话，那么我们需要一个数据结构维护各种话所产生的各物种的相对关系，所以自然想到要用并查集维护两个物种的关系，而且说了物种间会形成环，所以也需要并查集维护和判断，哪两个物种是成环的捕食关系。

我们假设根节点是在第0层，而能够捕食根节点的物种处在第一层，能够捕食第一层节点的物种在第二层，能够捕食第二层节点的物种在第三层………以此类推可以发现，捕食间相差距离为1，而根据成环我们可以推算出，a被b吃，b被c吃，如果只有三个物种且成环，那么c一定被a吃，看成层级关系的话就是第0层被第一层吃，第一层被第二层吃，而第二层恰好被第0层吃，也就是说距离为2的节点是被捕食关系，那距离为3的节点呢？
一共只有三种物种，且距离根节点为3距离的点会吃第二层的节点，所以我们发现规律距离为3的节点与第0层节点是同类，这个关系还可以向下推导，而方便书写我们就可以用取模代替。

也就是和根距离取模为1的为捕食关系，为2是被捕食关系，为0就是同类。

判断如果它说的这句话是某两个编号是同类，那么直接判断是否在一个集合里，如果在的话并且dxdy它们不同余，说明是假话，否则加入一个集合里，注意更新被合并也就是不再做祖先节点的那个点向另一个祖先节点连边的那条边权，画图可知，dpx+要更新的全值==dpy，因为它们是同一个物种所以边权相等那肯定同余，就用这个原理推出要更新的权值为dpy-dpx就是答案。

如果是捕食关系，首先也是判断是否在一个集合里，如果是则dy+1-dx必须同余，这里做差同余等同于分别判断同余，这是同余定理。

为什么是dy+1呢？因为x捕食y，x一定是在y下面一层，上面我们说过这个了，那么dy+1就是和dx同层了，它们相减的数字模3应该为0，因为dy+1后与dx同层对于根节点距离应该相等。

如果不在一个集合加入集合，并更新d值，此时d值是dy-dx+1，代码是x的祖先合入y祖先里，x比y大一层，dy-dx肯定是不够的要加1补充。

再看find函数的区别，由于我们合并数组值只更新到了祖先节点合并多出来的边的权值，所以在find一遍时候理应应该让那些没被更新的在之前的并查集的其他节点也发生更新，更新实际上是有模板的。

先用一个变量找到祖先节点，然后再更新dx加等上祖先节点权值，此时的x节点是距离根节点为1距离的点，然后更新并返回该祖先节点，回溯到上一层，上一层的原本距离为2的点，d值更新会是祖先节点权值+上一层x的权值，以此类推直到全部回溯，d都加上权值后返回祖先节点。

#include <iostream>
using namespace std;
const int N = 50010;
int p[N], n, m, d[N], t, x, y;
int find(int x)
{if (x != p[x]){int root = find(p[x]);d[x] += d[p[x]];p[x] = root;}return p[x];
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; ++ i ) p[i] = i;int ans = 0;while (m -- ){scanf("%d%d%d", &t, &x, &y);if (x > n || y > n ) {ans ++;continue;}int pa = find(x), pb = find(y);if (t == 1 ){if (pa == pb && (d[y] - d[x]) % 3 ) ans ++ ;else if (pa != pb){p[pa] = pb;d[pa] = d[y] - d[x];}}else{if (pa == pb && (d[y] + 1 - d[x]) % 3) ans ++;else if (pa != pb){p[pa] = pb;d[pa] = d[y] - d[x] + 1;}}}cout << ans;return 0;
}

第二道带权并查集

238. 银河英雄传说 - AcWing题库https://www.acwing.com/problem/content/240/这道题也是典型的带权并查集，要求的是某艘战舰距离它队头之间的战舰个数是多少，那很明显要维护同一个并查集的每个节点到该并查集队头的战舰个数，也就是祖先节点之间的，所以也是带权并查集的经典应用。

与上道题不同的是，这道题有两个额外数组，一个表示该集合目前共有多少个节点，也就是多少个战舰，一个代表一个集合里的其他战舰距离队头战舰间有多少个战舰。si数组要初始化，每个战舰在未合并到一个队伍里之前，每个战舰都是各成一个队伍，所以都是1。d数组是两个战舰间有几个，一开始都是0不用初始化。find函数的操作和上一道题一模一样，其实很多带权并查集的带权数组更新都是基本一样的模板，都是为了维护节点和祖先节点的关系。

si数组不在并查集函数里进行维护，只在需要合并两个并查集时候更新并查集节点个数，我们假设要把x祖先节点加入到y祖先节点里，那么把dpx更新为sipy，因为加入后，px距离py应该是相隔整个y并查集的战舰个数，然后让spy+=spx，再进行合并。

代码如下

#include <iostream>
using namespace std;
const int N = 30010;
int t, p[N], si[N], d[N];
int find(int x)
{if (x != p[x]){int root = find(p[x]);d[x] += d[p[x]];p[x] = root;}return p[x];
}
int main()
{cin >> t;for (int i = 1; i < N; ++ i ){p[i] = i;si[i] = 1;}for (int i = 0; i < t; ++ i ){char c; int x, y; cin >> c >> x >> y;if (c == 'M'){int pa = find(x), pb = find(y);if (pa != pb){d[pa] = si[pb];si[pb] += si[pa];p[pa] = pb;}}else{int pa = find(x), pb = find(y);if (pa != pb) puts("-1");else cout << max(0, abs(d[x] - d[y]) - 1) << endl;}}return 0;
}

第三道带权并查集

239. 奇偶游戏 - AcWing题库https://www.acwing.com/problem/content/241/这道题其实很相像第一道题，属于第一道的简化版，第一道有三种关系，第三道只有两种，分别为奇数性和偶数性，其实这道题也是很好的扩展域并查集题目，我们会在后面详细说明，代码的思路如何书写。

这道题的问题数目远小于序列n长度，暗示使用离散化。

回答l~r的区域内有多少个1其实就是问这中间前缀和是多少，因为数字序列不是0就是1，我们离散化取数字进行运算时也要去取到l-1和r的位置，l~r区域有奇数个1可以推出sr-sl-1是奇数，也可以推出sr和sl-1奇偶性不同，也就不用去写前缀和了，问题转化为看sr和si-1两个数奇偶性的比较，我们用数组d来表述每个元素和它的祖先节点的奇偶性关系，其中为0表示奇偶性相同，为1则不同。

如果两个数字在一个集合内，那么两个元素xy，它们的相对于祖先节点的奇偶性如果相同说明两个元素奇偶性相同，dxdy作异或，看和t也就是此时的答案是奇数个1还是偶数个1比较是否相等，t代表它这句话说的是奇数个1还是偶数个1，若不等直接输出并返回。
具体为如果t=0代表偶数个1，那么此时dxdy异或必须为0，代表它们奇偶性相等，才能异或为0。异或为1说明奇偶性不等，只有奇偶性相等减法才能为偶数，不等相减差应该为奇数。

然后是如果两个元素不在一个集合，那么它们的奇偶性为任意都可以，把它们合并在一个集合里，这里在不在一个集合里对于答案的判断影响可以这样思考，不在一个集合说明前面的回答没有提到这两个元素，那就肯定谈不上矛不矛盾，此时提到了将它们放在一个集合里，如果下次提到的时候在一个集合里，说明之前提到过，那么就要对回答就行判断，以防止出现矛盾，合并的d的更新，主要是更新合并后的祖先节点的d值，就是dx异或dy，当然还要对它们之间是否应该是相同奇偶性判断，这里主要判断t，所以异或上t就可以了。t为奇数就应该不同所以异或1，不同异或0。

异或不用考虑数据超范围，如果是相加和模上2也是可以的。

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
int n, m, p[N], d[N];
unordered_map<int, int> S;
int get(int x)
{if (S.count(x) == 0) S[x] = ++ n;return S[x];
}
int find(int x)
{if (x != p[x]){int root = find(p[x]);d[x] ^= d[p[x]];p[x] = root;}return p[x];
}
int main()
{cin >> n >> m;for (int i = 0; i < N; ++ i ) p[i] = i;n = 0;int ans = m;for (int i = 1; i <= m; ++ i ){int x, y; string s;cin >> x >> y >> s;x = get(x - 1), y = get(y);int t = 0;if (s == "odd") t = 1;int pa = find(x), pb = find(y);if (pa == pb){if ((d[x] ^ d[y]) != t){ans = i - 1;break;}}else{p[pa] = pb;d[pa] = d[x] ^ d[y] ^ t;}}cout << ans;return 0;
}

第四道带权并查集

1013-[NOIP2010]关押罪犯_2021秋季算法入门班第六章习题：搜索与搜索剪枝https://ac.nowcoder.com/acm/contest/23156/1013这道题带权和扩展域都可以做，且带权更容易理解。

主要思路就是两个过大的矛盾值要尽量避免，所以我们对矛盾值进行排序，把矛盾值大的先拿出来把它们放在不同监狱里，二分答案取最小的即可，并且约定如果两个罪犯不想把它们加进一个集合里，则它们对于祖先节点的距离模数不等，也就是模数应该一个等于0一个等于1，先判断如果两个罪犯的矛盾值大于我们枚举的最小矛盾值，那么要对它们进行处理，将一个合并到另一个集合里，并且把被合并进去的集合距离新祖先节点的值更新为原来值+被合并祖先节点值+1，其中的加1就是为了模拟不分同一个监狱里，如果本身就在一个并查集里，那么判断如果两个罪犯距离祖先节点值和模2为1则说明没有大冲突，如果不为1，说明在一个集合里，而且此时的矛盾是无法避免的了，直接break重新枚举二分答案。因为之前都是故意让它们值分开监狱，也就相当于奇偶性分开是一样道理，如果此时发现还是在一个监狱里说明是不得已了，直接返回答案就行。

这个d数组其实可以理解成奇偶游戏的d数组，同样也可以用异或方法存储距离，是一样的道理，故意把大的分成奇偶性质不同，直到下一次判断到两个数字奇偶性不同了，说明是假话，也就对应这里的起了冲突。

为什么故意这样设置奇偶分开也是会分到一个监狱里呢？

我们进行了排序所以每次都把较大的矛盾分开放监狱，但是每次会出现一种情况即a和b分开放，c和d分开放，但某时候a和c可能起冲突了，而ac恰好分在一起了，不得已起了冲突这是无法避免的，这也是很多题解没有讲明白的点，明白了这个也就明白了为什么故意这样设置也是会在某时刻有冲突出现。

这道题其实和奇偶一样，我认为扩展域并查集更好写和理解，当然前提是你要懂扩展域并查集。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{int x, y, k;bool operator<(const rec & b){return k > b.k;}
}q[maxn];
long long fa[maxn], d[maxn];
int ff(int x)
{if(fa[x] == x) return x;int r = ff(fa[x]);d[x] += d[fa[x]];return fa[x] = r;
}
int main()
{int n, m; cin >> n >> m;for(int i = 1; i <= m; i++){scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].k);}sort(q + 1, q + 1 + m);int l = 0, r = 1000000000;//int l = 0, r = 30000;while(l < r){int mid = (l + r) >> 1;int flag = 1;for(int i = 1; i <= n; i++) fa[i] = i;memset(d, 0, sizeof d);for(int i = 1; i <= m; i++){if(q[i].k > mid){int x = ff(q[i].x), y = ff(q[i].y);if(x == y){if((d[q[i].x] + d[q[i].y]) % 2 != 1){flag = 0;break;}}else{fa[x] = y;d[x] = d[q[i].x] +  d[q[i].y] + 1;}}}if(flag) r = mid;else l = mid + 1;}cout << l;return 0;
}

本期内容更新到这里，下一期是扩展域并查集的讲解，敬请期待！

制作不易，有用请三连支持！