1 问题
并查集 只能判断两个元素是否同属一个集合。现在还需要知道它们之间的差值。
设每个元素有一个未知数值
例如,已知
此时再加入差值为
绝对数值没有必要确定。把同一连通块中所有数值同时加上一个常数,差值不变。带权并查集选择根作为参考点,在父亲指针上保存相对差值。
2 边权
仍用 fa[x] 保存父亲,新增
根的父亲是自己,因此根的 d 为
fa[i] = i;
sz[i] = 1;
d[i] = 0;
若父亲链为
所以到根的差值等于父亲链上各段边权之和。
图中的
3 路径压缩
普通并查集只改父亲,带权并查集还要同步修改 d[x] 的含义。
先保存旧父亲 d[p] 已经变为
就得到 fa[x] 改为
int find(int x) {
if (fa[x] == x) return x;
int p = fa[x]; // 保存旧父亲
int root = find(p); // 先更新父亲到根的差值
d[x] += d[p]; // 再累计 x 到根的差值
fa[x] = root;
return root;
}
先累加旧父亲的权值,再改父亲。 若先把 fa[x] 改为根,再读取 d[fa[x]],读到的就是根的
调用 find(x) 后,d[x] 才保证表示到当前根的差值。其他未访问节点仍可能保存到父亲的差,不能把整个数组都当成“到根距离”。
4 差值查询
先对两端执行 find。若根相同,根的参考值可以相消:
int fx = find(x), fy = find(y);
if (fx != fy) {
// 差值未知
} else {
// V[y] - V[x] = d[y] - d[x]
}
根不同时,两个集合可以独立平移,它们之间的差值尚未确定。此时不能直接用 d[y] - d[x],即使两个值恰好都是零。
5 合并公式
5.1 连接两个根
加入 find(x)、find(y),得到根
假设让
已知
代入新约束:
移项得到
例如 d[x]=3、d[y]=-1、
恰好满足约束。其他节点的局部边权不用逐个修改,之后查询时再沿路径累加。
5.2 反向连接
按大小合并可能要求
因此可以先计算一个方向的 delta;交换两个根时,同时令 delta = -delta。只交换根、不改变权值符号,会把新约束反向。
5.3 已经同根
若两端已经同根,差值已经确定,不再连接根:
if (fx == fy) return d[y] - d[x] == w;
差值相同,约束只是重复确认;差值不同,拒绝本条约束。不要改写根的权值去“修正”差值,否则会破坏之前的关系。
6 代码
本篇使用以下在线格式。第一行输入
0 x y w:尝试加入;相容输出 YES并接受,矛盾输出NO并拒绝。1 x y:输出;关系尚未确定则输出 UNKNOWN。
这里 add_relation 返回的是“约束是否相容”,包括相容的重复约束,不是“是否减少了一个集合”。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
int fa[maxn], sz[maxn];
ll d[maxn]; // d[x] = V[x] - V[fa[x]];find(x) 后变为到根的差
void init(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
d[i] = 0;
}
}
int find(int x) {
if (fa[x] == x) return x;
int p = fa[x]; // 保存旧父亲
int root = find(p); // 先让 d[p] 变为 V[p] - V[root]
d[x] += d[p]; // 两段相加,得到 V[x] - V[root]
fa[x] = root;
return root;
}
// 尝试加入 V[y] - V[x] = w;相容则接受,矛盾则拒绝。
bool add_relation(int x, int y, ll w) {
int fx = find(x), fy = find(y);
if (fx == fy) return d[y] - d[x] == w;
ll delta = w + d[x] - d[y]; // V[fy] - V[fx]
if (sz[fx] < sz[fy]) {
swap(fx, fy);
delta = -delta; // 连接方向反转,差值也必须反号
}
fa[fy] = fx;
d[fy] = delta;
sz[fx] += sz[fy];
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
init(n);
while (m--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 0) {
ll w;
cin >> w;
cout << (add_relation(x, y, w) ? "YES" : "NO") << '\n';
} else {
int fx = find(x), fy = find(y);
if (fx != fy) cout << "UNKNOWN\n";
else cout << d[y] - d[x] << '\n';
}
}
return 0;
}
输入:
5 10
0 1 2 3
0 2 3 -1
1 1 3
0 1 3 2
0 1 3 5
1 1 3
0 4 3 7
1 4 2
1 1 5
0 5 5 1
输出:
YES
YES
2
YES
NO
2
YES
8
UNKNOWN
NO
第五条约束被拒绝,
此时元素
7 正确性与复杂度
始终维护:父亲边保存对应的数值差,树中已有约束全部成立。
初始化时,每个点独立,根的差为零。路径压缩利用差值的可加性,将多段差合成一段,保留节点到根的相对值。
合并两个集合时,它们原本可以独立平移。按推导出的根间差值连接,相当于确定两个参考系之间的偏移;集合内部的差值不变,新约束也成立。
同根时,两点间的差已经由树唯一确定。检查它是否等于
主模板采用路径压缩与按大小合并,初始化
8 队列拼接
8.1 银河英雄传说
luogu P1196: [NOI2002] 银河英雄传说 中,每艘战舰初始独立成列,支持:
M x y:把所在的整列接到 所在列的尾部,保持两列内部顺序。 C x y:若两艘战舰同列,查询它们中间的战舰数;不同列返回。
保留“根是队首”的表示。sz[root] 为整列长度,d[x] 保存 find(x) 后,d[x] 就是
设
fa[fx] = fy;
d[fx] = sz[fy];
sz[fy] += sz[fx];
这里的根间差由队列长度决定。它是拼接操作带来的位移,不是读入一个固定的两点差值约束。
图中原来的两列为 M 1 3,得到 fa[2]=4、d[2]=2;战舰
8.2 合并方向
主模板中的根只是任选的参考点,可以按大小选择;本例却要求根始终是队首,必须将
不能交换两个根后仍沿用上述赋值。 否则可能颠倒拼接方向,或破坏“根为队首、根的差为零”的约定。
合并方向固定,树可能很深。下面的完整代码使用两遍非递归路径压缩:先求总差,再沿原路径更新各节点。它与递归版遵循同一个边权不变量,可以避免深链造成递归栈过深。
8.3 查询
同列且
位置差包含相邻两舰间的一步,中间元素数要再减一;相邻战舰的答案为
银河英雄传说完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30000 + 5;
int fa[maxn], sz[maxn], d[maxn];
void init() {
for (int i = 1; i <= 30000; ++i) {
fa[i] = i;
sz[i] = 1;
d[i] = 0;
}
}
// 两遍路径压缩,避免固定合并方向形成深链后递归栈过深。
int find(int x) {
int root = x, total = 0;
while (fa[root] != root) {
total += d[root];
root = fa[root];
}
while (x != root) {
int p = fa[x], old = d[x];
fa[x] = root;
d[x] = total; // 当前节点到队首的距离
total -= old; // 下一节点原本到根的距离
x = p;
}
return root;
}
// 把 x 所在队列整体接到 y 所在队列尾部,根始终表示队首。
void append(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy;
d[fx] = sz[fy]; // x 队列的旧队首向后平移 y 队列的长度
sz[fy] += sz[fx];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int m;
cin >> m;
while (m--) {
char op;
int x, y;
cin >> op >> x >> y;
if (op == 'M') append(x, y);
else {
int fx = find(x), fy = find(y);
if (fx != fy) cout << -1 << '\n';
else cout << abs(d[x] - d[y]) - 1 << '\n'; // 原题保证 x != y
}
}
return 0;
}
原题共有
输入:
8
M 1 2
M 3 4
M 1 3
C 1 4
C 2 3
C 1 5
M 5 2
C 5 3
输出:
2
0
-1
2
本例只使用路径压缩,没有按大小合并。设战舰数为
9 模关系
种类并查集 用多个身份表示类别关系。也可以给类别编号,在模
- 两类关系:差为
表示同类,差为 表示异类。 - 三类循环:差为
,分别表示三种相对关系,具体方向要先约定。
推导仍遵循“节点到父亲的差可以相加”,但每次运算都要按模 (v % k + k) % k。
这说明拆点与带权是表达相对关系的两种方式。初学时可先用拆点明确对应关系,再用边权减少辅助节点。
10 易错点
- 差值方向统一。 本篇始终规定
,输入约束为 。采用其他约定时必须重新推导。 - 先查根,再读差。 未访问节点的
d仍可能只表示到父亲的差。 - 反向合并取反。
swap(fx, fy)必须同时改变根间差值的符号。 - 负数合法。 不能对一般差值查询取绝对值;银河英雄传说取绝对值,是因为它查询两位置之间的间隔。
- 宽类型。 主模板的
d、输入权值和中间加减使用ll,仍需保证累积差值不溢出。 - 检查新关系。 同根不代表新约束一定相容,必须比较已知差值。
- 多组数据。 重新初始化
fa、sz和d,根的初始权值为零。
11 练习
11.1 手算
- 已知
、 , 是多少? - 若把
接到 时应记录权值 ,反向连接要记录多少? - 两个独立根的
d都为零,能否推出它们的数值相同?
参考结果
。差值有方向,不取绝对值。 。 - 不能。各自的零只表示“相对自身的差为零”,两个参考系之间尚无联系。
11.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 差值查询 | AOJ DSL_1_B:Weighted Union Find Trees | 直接维护 ?;题目保证约束不矛盾。 |
| 一致性 | AtCoder ABC087 D:People on a Line | 给出位置差,判断全部约束能否同时满足;出现任何矛盾,整体答案为否。 |
| 逐条接受 | AtCoder ABC328 F:Good Set Query | 按顺序接受相容约束,输出被接受的编号。题目是 (b,a,d),注意差值方向。 |
| 队列位移 | luogu P1196: [NOI2002] 银河英雄传说 | 用队列长度确定根间权值,区分固定拼接方向与一般按大小合并。 |
12 参考
- Princeton:Union-Find 讲义:区分单独路径压缩与双优化的复杂度界。
13 相关题解
暂无相关题解