带权并查集

1 问题

并查集 只能判断两个元素是否同属一个集合。现在还需要知道它们之间的差值。

设每个元素有一个未知数值 V[x]V[x],依次加入约束

V[y]−V[x]=w. V[y]-V[x]=w.

例如,已知 V[2]−V[1]=3V[2]-V[1]=3、V[3]−V[2]=−1V[3]-V[2]=-1,就能推出

V[3]−V[1]=3+(−1)=2. V[3]-V[1]=3+(-1)=2.

此时再加入差值为 22 的相同约束,仍然相容;若要求差值为 55,则产生冲突。

绝对数值没有必要确定。把同一连通块中所有数值同时加上一个常数,差值不变。带权并查集选择根作为参考点,在父亲指针上保存相对差值。

2 边权

仍用 fa[x] 保存父亲,新增

d[x]=V[x]−V[fa[x]]. d[x]=V[x]-V[fa[x]].

根的父亲是自己,因此根的 d 为 00。初始时,每个元素单独成集:

fa[i] = i;
sz[i] = 1;
d[i] = 0;

若父亲链为 x→p→rx\to p\to r,则

V[x]−V[r]=(V[x]−V[p])+(V[p]−V[r]). V[x]-V[r] =\bigl(V[x]-V[p]\bigr)+\bigl(V[p]-V[r]\bigr).

所以到根的差值等于父亲链上各段边权之和。

父亲链上两段权值为二和五,压缩后到根的权值变为七

图中的 2,52,5 相加得到 77。这里的“权”可以为负数,表示有方向的差值,不一定是几何距离,也不是集合大小。

3 路径压缩

普通并查集只改父亲,带权并查集还要同步修改 d[x] 的含义。

先保存旧父亲 pp,递归将 pp 接到根 rr。这时 d[p] 已经变为 V[p]−V[r]V[p]-V[r],再执行

d[x]←d[x]+d[p], d[x]\gets d[x]+d[p],

就得到 V[x]−V[r]V[x]-V[r],可以把 fa[x] 改为 rr。

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]],读到的就是根的 00,会漏掉原父亲到根的那一段。

调用 find(x) 后,d[x] 才保证表示到当前根的差值。其他未访问节点仍可能保存到父亲的差,不能把整个数组都当成“到根距离”。

4 差值查询

先对两端执行 find。若根相同,根的参考值可以相消:

V[y]−V[x]=(V[y]−V[r])−(V[x]−V[r])=d[y]−d[x]. V[y]-V[x] =\bigl(V[y]-V[r]\bigr)-\bigl(V[x]-V[r]\bigr) =d[y]-d[x].
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 连接两个根

加入 V[y]−V[x]=wV[y]-V[x]=w,先执行 find(x)、find(y),得到根 fx,fyf_x,f_y。

假设让 fyf_y 接到 fxf_x 下面,需要填写的是

d[fy]=V[fy]−V[fx]. d[f_y]=V[f_y]-V[f_x].

已知

V[x]=V[fx]+d[x],V[y]=V[fy]+d[y]. V[x]=V[f_x]+d[x],\qquad V[y]=V[f_y]+d[y].

代入新约束:

(V[fy]+d[y])−(V[fx]+d[x])=w. \bigl(V[f_y]+d[y]\bigr)-\bigl(V[f_x]+d[x]\bigr)=w.

移项得到

d[fy]=w+d[x]−d[y]. \boxed{d[f_y]=w+d[x]-d[y]}.

把 fy 接到 fx 后,根间差值为八,结合两端原有差值三和负一,得到新约束四

例如 d[x]=3、d[y]=-1、w=4w=4,则根间差值为 4+3−(−1)=84+3-(-1)=8。沿新树计算

V[y]−V[x]=−1+8−3=4, V[y]-V[x]=-1+8-3=4,

恰好满足约束。其他节点的局部边权不用逐个修改,之后查询时再沿路径累加。

5.2 反向连接

按大小合并可能要求 fxf_x 接到 fyf_y。连接方向反过来,保存的差也要取反:

d[fx]=V[fx]−V[fy]=d[y]−d[x]−w. d[f_x]=V[f_x]-V[f_y]=d[y]-d[x]-w.

因此可以先计算一个方向的 delta;交换两个根时,同时令 delta = -delta。只交换根、不改变权值符号,会把新约束反向。

5.3 已经同根

若两端已经同根,差值已经确定,不再连接根:

if (fx == fy) return d[y] - d[x] == w;

差值相同,约束只是重复确认;差值不同,拒绝本条约束。不要改写根的权值去“修正”差值,否则会破坏之前的关系。

6 代码

本篇使用以下在线格式。第一行输入 n,mn,m,接下来处理 mm 次操作:

  • 0 x y w:尝试加入 V[y]−V[x]=wV[y]-V[x]=w;相容输出 YES 并接受,矛盾输出 NO 并拒绝。
  • 1 x y:输出 V[y]−V[x]V[y]-V[x];关系尚未确定则输出 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

第五条约束被拒绝,V[3]−V[1]V[3]-V[1] 仍为 22。加入 V[3]−V[4]=7V[3]-V[4]=7 后,

V[2]−V[4]=(V[2]−V[3])+(V[3]−V[4])=1+7=8. V[2]-V[4] =\bigl(V[2]-V[3]\bigr)+\bigl(V[3]-V[4]\bigr) =1+7=8.

此时元素 55 仍独立,无法查询它与 11 的差。最后一条要求 V[5]−V[5]=1V[5]-V[5]=1,与自差为零矛盾。

7 正确性与复杂度

始终维护:父亲边保存对应的数值差,树中已有约束全部成立。

初始化时,每个点独立,根的差为零。路径压缩利用差值的可加性,将多段差合成一段,保留节点到根的相对值。

合并两个集合时,它们原本可以独立平移。按推导出的根间差值连接,相当于确定两个参考系之间的偏移;集合内部的差值不变,新约束也成立。

同根时,两点间的差已经由树唯一确定。检查它是否等于 ww,恰好判断新约束是否矛盾。拒绝约束时,除不改变关系的路径压缩外,不修改已有状态。

主模板采用路径压缩与按大小合并,初始化 O(n)O(n),mm 次操作总时间为 O(n+mα(n))O(n+m\alpha(n)),空间为 O(n)O(n)。模板支持 n≤2×105n\le2\times10^5。

8 队列拼接

8.1 银河英雄传说

luogu P1196: [NOI2002] 银河英雄传说 中,每艘战舰初始独立成列,支持:

  • M x y:把 xx 所在的整列接到 yy 所在列的尾部,保持两列内部顺序。
  • C x y:若两艘战舰同列,查询它们中间的战舰数;不同列返回 −1-1。

保留“根是队首”的表示。sz[root] 为整列长度,d[x] 保存 xx 相对父亲的位置差;find(x) 后,d[x] 就是 xx 前面的战舰数。

设 x,yx,y 所在列的根为 fx,fyf_x,f_y。拼接后,新队首仍是 fyf_y,旧队首 fxf_x 向后移动 yy 列的长度,因此

fa[fx] = fy;
d[fx] = sz[fy];
sz[fy] += sz[fx];

这里的根间差由队列长度决定。它是拼接操作带来的位移,不是读入一个固定的两点差值约束。

把二一队列接到四三队列后面,原队首二向后移动两格

图中原来的两列为 [2,1][2,1]、[4,3][4,3]。执行 M 1 3,得到 [4,3,2,1][4,3,2,1]。令 fa[2]=4、d[2]=2;战舰 11 原来距队首 22 一格,之后距新队首就是 1+2=31+2=3 格。

8.2 合并方向

主模板中的根只是任选的参考点,可以按大小选择;本例却要求根始终是队首,必须将 fxf_x 接到 fyf_y。

不能交换两个根后仍沿用上述赋值。 否则可能颠倒拼接方向,或破坏“根为队首、根的差为零”的约定。

合并方向固定,树可能很深。下面的完整代码使用两遍非递归路径压缩:先求总差,再沿原路径更新各节点。它与递归版遵循同一个边权不变量,可以避免深链造成递归栈过深。

8.3 查询

同列且 x≠yx\ne y 时,

中间战舰数=∣d[x]−d[y]∣−1. \text{中间战舰数}=\lvert d[x]-d[y]\rvert-1.

位置差包含相邻两舰间的一步,中间元素数要再减一;相邻战舰的答案为 00。

银河英雄传说完整代码
#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;
}

原题共有 3000030000 艘战舰,保证每次合并的两列不同,查询中的两个编号也不同。代码中的同根保护避免重复拼接,但不改变原题接口。

输入:

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

本例只使用路径压缩,没有按大小合并。设战舰数为 NN、操作数为 mm,采用一般上界 O((N+m)log⁡N)O((N+m)\log N);单次操作最坏仍可能为 O(N)O(N),不能直接沿用主模板的双优化均摊界。空间为 O(N)O(N)。

9 模关系

种类并查集 用多个身份表示类别关系。也可以给类别编号,在模 kk 意义下维护差值:

  • 两类关系:差为 00 表示同类,差为 11 表示异类。
  • 三类循环:差为 0,1,20,1,2,分别表示三种相对关系,具体方向要先约定。

推导仍遵循“节点到父亲的差可以相加”,但每次运算都要按模 kk 处理。C++ 中负数取模可能为负,应规范为 (v % k + k) % k。

这说明拆点与带权是表达相对关系的两种方式。初学时可先用拆点明确对应关系,再用边权减少辅助节点。

10 易错点

  • 差值方向统一。 本篇始终规定 d[x]=V[x]−V[fa[x]]d[x]=V[x]-V[fa[x]],输入约束为 V[y]−V[x]=wV[y]-V[x]=w。采用其他约定时必须重新推导。
  • 先查根,再读差。 未访问节点的 d 仍可能只表示到父亲的差。
  • 反向合并取反。 swap(fx, fy) 必须同时改变根间差值的符号。
  • 负数合法。 不能对一般差值查询取绝对值;银河英雄传说取绝对值,是因为它查询两位置之间的间隔。
  • 宽类型。 主模板的 d、输入权值和中间加减使用 ll,仍需保证累积差值不溢出。
  • 检查新关系。 同根不代表新约束一定相容,必须比较已知差值。
  • 多组数据。 重新初始化 fa、sz 和 d,根的初始权值为零。

11 练习

11.1 手算

  1. 已知 V[2]−V[1]=4V[2]-V[1]=4、V[3]−V[2]=−6V[3]-V[2]=-6,V[3]−V[1]V[3]-V[1] 是多少?
  2. 若把 fyf_y 接到 fxf_x 时应记录权值 88,反向连接要记录多少?
  3. 两个独立根的 d 都为零,能否推出它们的数值相同?
参考结果
  1. −2-2。差值有方向,不取绝对值。
  2. −8-8。
  3. 不能。各自的零只表示“相对自身的差为零”,两个参考系之间尚无联系。

11.2 推荐题目

层次 题目 训练内容
差值查询 AOJ DSL_1_B:Weighted Union Find Trees 直接维护 V[y]−V[x]V[y]-V[x]。下标从 00 开始,加入约束不输出,未知差值输出 ?;题目保证约束不矛盾。
一致性 AtCoder ABC087 D:People on a Line 给出位置差,判断全部约束能否同时满足;出现任何矛盾,整体答案为否。
逐条接受 AtCoder ABC328 F:Good Set Query 按顺序接受相容约束,输出被接受的编号。题目是 Xa−Xb=dX_a-X_b=d,调用本篇接口时可传入 (b,a,d),注意差值方向。
队列位移 luogu P1196: [NOI2002] 银河英雄传说 用队列长度确定根间权值,区分固定拼接方向与一般按大小合并。

12 参考

13 相关题解

暂无相关题解