并查集进阶题解带权并查集与种类并查集食物链与等式方程的可满足性在并查集的基础题型中我们处理的通常是简单的“是否在同一个连通块二元连通关系”。但在算法竞赛与各大厂顶级高难度算法面试中题目的关系维度往往会被极大拓宽LeetCode 990等式方程的可满足性Equality EquationsLeetCode 399除法求值Evaluate Division带权并查集经典神题食物链POJ 1182 / 种类并查集三元相克食物链关系。在这些题目中节点之间不仅要维护“是否相连”还要维护节点之间的相对权值倍数Weight Ratio或多向敌对/同盟的相对种类关系Offset Relation。很多同学在面对这类进阶问题时不知道如何在路径压缩find和集合合并union时同步更新权重向量。今天我们把带权并查集Weighted Union-Find与种类并查集Disjoint Set with Offsets的数学向量推导与代码实现彻底拆解清楚。一、带权并查集在路径压缩中维护相对权值LeetCode 399 除法求值题目背景给定一组变量除法等式A / B 2.0,B / C 3.0。求任意给定的查询A / C ?的值。数学向量模型设每个节点 $x$ 维护一个权重weight[x]其严格物理含义为$$\mathbf{\text{weight}[x] \frac{x}{\text{parent}[x]}}$$即节点 $x$ 的值是其父节点 $\text{parent}[x]$ 的多少倍graph TD subgraph 路径压缩前 A((A)) --|weight[A] 2.0 (A/B)| B((B)) B --|weight[B] 3.0 (B/C)| C((C: 根)) end subgraph 路径压缩后 (Direct Link to Root) A2((A)) --|new_weight[A] 2.0 * 3.0 6.0 (A/C)| C2((C: 根)) B2((B)) --|weight[B] 3.0| C2 end1. 带权路径压缩find时的权值累乘当把节点 $x$ 的父节点直接指向根节点root时根据除法链式法则$$\frac{x}{\text{root}} \frac{x}{\text{origin_parent}} \times \frac{\text{origin_parent}}{\text{root}}$$因此新的weight[x]等于其原本的权重乘以原父节点压缩后的权重public int find(int x) { if (parent[x] ! x) { int originParent parent[x]; parent[x] find(parent[x]); // 递归压缩父节点 weight[x] * weight[originParent]; // 权值累乘更新 } return parent[x]; }2. 带权合并union时的桥接权值推导已知 $A$ 的根为 $R_A$$B$ 的根为 $R_B$且给定 $A / B v$我们要将 $R_A$ 挂到 $R_B$ 下面parent[rootA] rootB那么新连接的边权 $\text{weight}[R_A] \frac{R_A}{R_B}$ 应该等于多少根据代数等式$$\frac{R_A}{R_B} \frac{R_A}{A} \times \frac{A}{B} \times \frac{B}{R_B} \frac{1}{\text{weight}[A]} \times v \times \text{weight}[B]$$因此$$\mathbf{\text{weight}[\text{rootA}] \frac{v \times \text{weight}[B]}{\text{weight}[A]}}$$public void union(int a, int b, double value) { int rootA find(a); int rootB find(b); if (rootA ! rootB) { parent[rootA] rootB; weight[rootA] (value * weight[b]) / weight[a]; // 精准公式赋值 } }二、种类并查集扩展域Extended Elements思想当节点之间的关系是“二元对立敌对关系”或“三元食物链A 吃 BB 吃 CC 吃 A”时最优雅的工业级解法是扩展域并查集Multiple-domain DSU。核心思想为每个实体虚拟出多个维度的“镜像节点”以经典的“食物链三元循环”为例每个动物 $i$ 虚拟出 3 个维度的身份$i$代表 $i$ 自身的同类域$i N$代表 $i$ 的捕食域被 $i$ 吃的物种$i 2N$代表 $i$ 的天敌域吃 $i$ 的物种。graph LR subgraph 实体 1 的三维虚拟域 A1[1: 同类] --- B1[1N: 捕食对象] B1 --- C1[12N: 天敌] end subgraph 表达 1 吃 2 的逻辑绑定 A1 -.-|union| B2[22N: 2 的天敌即为 1] B1 -.-|union| A2[2: 1 的猎物即为 2] C1 -.-|union| C2[2N: 1 的天敌即为 2 的猎物] end逻辑推理的并查集映射断言“$A$ 与 $B$ 是同类”检查矛盾$A$ 不能在 $B$ 的捕食域或天敌域中find(A) find(BN) || find(A) find(B2N)则为谎言合并三组同盟union(A, B),union(AN, BN),union(A2N, B2N)断言“$A$ 吃 $B$”检查矛盾$A$ 不能是 $B$ 的同类也不能被 $B$ 吃合并因果关系union(AN, B)$A$ 的猎物是 $B$、union(A, B2N)$B$ 的天敌是 $A$、union(A2N, BN)。复杂度分析与总结带权并查集在路径压缩和合并中仅增加了常数次浮点乘除运算时间复杂度依然保持为严格的 $\mathcal{O}(M \alpha(N))$种类并查集将数组空间扩大为 $3N$或 $2N$利用标准并查集的所有操作将复杂的逻辑关系判定完全转化为连通分量的等价性检验。掌握了带权除法链式法则与扩展域镜像思想所有涉及多维约束、敌友关系与相对倍率的图论题目都将迎刃而解。 并查集进阶题解：带权并查集与种类并查集（食物链与等式方程的可满足性）
并查集进阶题解带权并查集与种类并查集食物链与等式方程的可满足性在并查集的基础题型中我们处理的通常是简单的“是否在同一个连通块二元连通关系”。但在算法竞赛与各大厂顶级高难度算法面试中题目的关系维度往往会被极大拓宽LeetCode 990等式方程的可满足性Equality EquationsLeetCode 399除法求值Evaluate Division带权并查集经典神题食物链POJ 1182 / 种类并查集三元相克食物链关系。在这些题目中节点之间不仅要维护“是否相连”还要维护节点之间的相对权值倍数Weight Ratio或多向敌对/同盟的相对种类关系Offset Relation。很多同学在面对这类进阶问题时不知道如何在路径压缩find和集合合并union时同步更新权重向量。今天我们把带权并查集Weighted Union-Find与种类并查集Disjoint Set with Offsets的数学向量推导与代码实现彻底拆解清楚。一、带权并查集在路径压缩中维护相对权值LeetCode 399 除法求值题目背景给定一组变量除法等式A / B 2.0,B / C 3.0。求任意给定的查询A / C ?的值。数学向量模型设每个节点 $x$ 维护一个权重weight[x]其严格物理含义为$$\mathbf{\text{weight}[x] \frac{x}{\text{parent}[x]}}$$即节点 $x$ 的值是其父节点 $\text{parent}[x]$ 的多少倍graph TD subgraph 路径压缩前 A((A)) --|weight[A] 2.0 (A/B)| B((B)) B --|weight[B] 3.0 (B/C)| C((C: 根)) end subgraph 路径压缩后 (Direct Link to Root) A2((A)) --|new_weight[A] 2.0 * 3.0 6.0 (A/C)| C2((C: 根)) B2((B)) --|weight[B] 3.0| C2 end1. 带权路径压缩find时的权值累乘当把节点 $x$ 的父节点直接指向根节点root时根据除法链式法则$$\frac{x}{\text{root}} \frac{x}{\text{origin_parent}} \times \frac{\text{origin_parent}}{\text{root}}$$因此新的weight[x]等于其原本的权重乘以原父节点压缩后的权重public int find(int x) { if (parent[x] ! x) { int originParent parent[x]; parent[x] find(parent[x]); // 递归压缩父节点 weight[x] * weight[originParent]; // 权值累乘更新 } return parent[x]; }2. 带权合并union时的桥接权值推导已知 $A$ 的根为 $R_A$$B$ 的根为 $R_B$且给定 $A / B v$我们要将 $R_A$ 挂到 $R_B$ 下面parent[rootA] rootB那么新连接的边权 $\text{weight}[R_A] \frac{R_A}{R_B}$ 应该等于多少根据代数等式$$\frac{R_A}{R_B} \frac{R_A}{A} \times \frac{A}{B} \times \frac{B}{R_B} \frac{1}{\text{weight}[A]} \times v \times \text{weight}[B]$$因此$$\mathbf{\text{weight}[\text{rootA}] \frac{v \times \text{weight}[B]}{\text{weight}[A]}}$$public void union(int a, int b, double value) { int rootA find(a); int rootB find(b); if (rootA ! rootB) { parent[rootA] rootB; weight[rootA] (value * weight[b]) / weight[a]; // 精准公式赋值 } }二、种类并查集扩展域Extended Elements思想当节点之间的关系是“二元对立敌对关系”或“三元食物链A 吃 BB 吃 CC 吃 A”时最优雅的工业级解法是扩展域并查集Multiple-domain DSU。核心思想为每个实体虚拟出多个维度的“镜像节点”以经典的“食物链三元循环”为例每个动物 $i$ 虚拟出 3 个维度的身份$i$代表 $i$ 自身的同类域$i N$代表 $i$ 的捕食域被 $i$ 吃的物种$i 2N$代表 $i$ 的天敌域吃 $i$ 的物种。graph LR subgraph 实体 1 的三维虚拟域 A1[1: 同类] --- B1[1N: 捕食对象] B1 --- C1[12N: 天敌] end subgraph 表达 1 吃 2 的逻辑绑定 A1 -.-|union| B2[22N: 2 的天敌即为 1] B1 -.-|union| A2[2: 1 的猎物即为 2] C1 -.-|union| C2[2N: 1 的天敌即为 2 的猎物] end逻辑推理的并查集映射断言“$A$ 与 $B$ 是同类”检查矛盾$A$ 不能在 $B$ 的捕食域或天敌域中find(A) find(BN) || find(A) find(B2N)则为谎言合并三组同盟union(A, B),union(AN, BN),union(A2N, B2N)断言“$A$ 吃 $B$”检查矛盾$A$ 不能是 $B$ 的同类也不能被 $B$ 吃合并因果关系union(AN, B)$A$ 的猎物是 $B$、union(A, B2N)$B$ 的天敌是 $A$、union(A2N, BN)。复杂度分析与总结带权并查集在路径压缩和合并中仅增加了常数次浮点乘除运算时间复杂度依然保持为严格的 $\mathcal{O}(M \alpha(N))$种类并查集将数组空间扩大为 $3N$或 $2N$利用标准并查集的所有操作将复杂的逻辑关系判定完全转化为连通分量的等价性检验。掌握了带权除法链式法则与扩展域镜像思想所有涉及多维约束、敌友关系与相对倍率的图论题目都将迎刃而解。