每日算法 — 使用java实现带权并查集：路径压缩与差分约束的集合合并

引言

并查集（Union-Find）是处理不相交集合合并与查询问题的经典数据结构，其近乎常数时间复杂度的操作效率使其在图论、聚类分析等领域大放异彩。普通并查集只能回答”两个元素是否属于同一集合”，而带权并查集通过维护节点到父节点的权值关系，可以回答”两个元素之间的相对关系”，如差值、比例等。本文将深入讲解带权并查集的原理，并应用到食物链判定和差分约束求解两个经典问题中。

核心算法概述

1. 普通并查集的优化

普通并查集通过路径压缩和按秩合并，将单次操作均摊复杂度降至接近O(α(n))，其中α是阿克曼函数的反函数，实际应用中可视为常数。

2. 带权并查集的核心思想

在普通并查集的基础上，为每个节点维护一个weight值，表示该节点到其父节点的”距离”或”关系”。当两个节点合并时，不仅合并它们的集合，还建立两者之间的权值关系。查询时，通过路径压缩同时更新权值，使得每个节点直接指向根节点，且权值表示到根节点的累计关系。

3. 差分约束系统

差分约束系统是一组形如 x_i - x_j ≤ c_k 的不等式。通过引入超级源点，可以将其转化为图中的最短路径问题，用SPFA或Bellman-Ford算法求解。带权并查集也可以处理部分特殊的差分约束。

Java完整实现

import java.util.*;

/**
 * 带权并查集实现
 * 维护节点到根节点的累积权值，支持关系查询
 */
class WeightedUnionFind {
    private int[] parent;
    private int[] rank;
    private long[] weight; // weight[i]表示节点i到parent[i]的权值
    private int count; // 连通分量数

    public WeightedUnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        weight = new long[n];
        count = n;

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
            weight[i] = 0; // 自己到自己的权值为0
        }
    }

    /**
     * 查找根节点（带路径压缩）
     * 路径压缩时同步更新权值
     */
    public int find(int x) {
        if (parent[x] != x) {
            int root = find(parent[x]);
            // 权值传递：x到根 = x到父节点 + 父节点到根
            weight[x] += weight[parent[x]];
            parent[x] = root;
        }
        return parent[x];
    }

    /**
     * 获取节点x到其根节点的累积权值
     * 注意：调用前应先执行find(x)确保路径已压缩
     */
    public long getWeight(int x) {
        find(x); // 确保路径压缩
        return weight[x];
    }

    /**
     * 合并两个节点，并建立它们之间的权值关系
     * 关系：value[y] - value[x] = w
     * @param x 节点x
     * @param y 节点y
     * @param w 权值差（y相对于x的权值差）
     * @return 如果x和y已在同一集合且关系矛盾，返回false
     */
    public boolean union(int x, int y, long w) {
        int rootX = find(x);
        int rootY = find(y);
        long weightX = weight[x]; // x到rootX的权值
        long weightY = weight[y]; // y到rootY的权值

        if (rootX == rootY) {
            // 已在同一集合，检查关系是否一致
            // 期望：weightY - weightX == w
            return (weightY - weightX) == w;
        }

        // 按秩合并：将小树合并到大树下
        // 需要满足：合并后 weight[y] - weight[x] = w
        // 即：(weightY + delta) - weightX = w
        // 得：delta = w + weightX - weightY
        // delta是新rootY的权值（相对于rootX）

        if (rank[rootX] < rank[rootY]) {
            // 将rootX挂到rootY下
            // rootX的权值 = w + weightX - weightY的相反数？
            // 重新推导：合并后find(x)和find(y)应该有相同根
            // 设rootX挂到rootY下，weight[rootX] = ?
            // 对任意节点：value[node] = base + weight[node]
            // 合并后要求：baseY + weightY - (baseX + weightX) = w
            // 新base相同，设rootX的权值为delta
            // 则：(weightY) - (weightX + delta) = w
            // delta = weightY - weightX - w
            parent[rootX] = rootY;
            weight[rootX] = weightY - weightX - w;
            rank[rootY] += rank[rootX];
        } else {
            // 将rootY挂到rootX下
            // weightY + delta - weightX = w
            // delta = w + weightX - weightY
            parent[rootY] = rootX;
            weight[rootY] = w + weightX - weightY;
            rank[rootX] += rank[rootY];
        }

        count--;
        return true;
    }

    /**
     * 查询x和y之间的关系差
     * 返回值表示：value[y] - value[x]
     * 如果x和y不在同一集合，返回Long.MIN_VALUE
     */
    public Long queryDifference(int x, int y) {
        if (find(x) != find(y)) {
            return null; // 不在同一集合
        }
        return weight[y] - weight[x];
    }

    /**
     * 判断两个节点是否连通
     */
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() {
        return count;
    }
}

/**
 * 经典应用1：食物链问题（POJ 1182）
 * 三种动物A、B、C构成食物链，A吃B，B吃C，C吃A
 * 给定N个动物和K句话，判断有多少句是假话
 */
class FoodChainSolver {
    /**
     * 解题思路：使用扩展域并查集（带权并查集）
     * 每个动物i拆分为三个节点：i(自身), i+N(捕食者), i+2N(被捕食者)
     * 或者用带权并查集，权值模3表示关系：0=同类，1=捕食，2=被捕食
     */
    public static int solve(int n, int[][] statements) {
        // 使用带权并查集，weight[i]表示i到根的关系（模3）
        // 0: 同类, 1: i被根吃, 2: i吃根
        WeightedUnionFindMod3 wuf = new WeightedUnionFindMod3(n + 1);
        int lies = 0;

        for (int[] stmt : statements) {
            int type = stmt[0]; // 1=同类，2=捕食
            int x = stmt[1];
            int y = stmt[2];

            // 超出范围即为假话
            if (x > n || y > n) {
                lies++;
                continue;
            }

            if (type == 1) {
                // x和y是同类
                // 如果已知x和y有关系且不是同类，则为假话
                if (wuf.connected(x, y)) {
                    Long diff = wuf.queryDifference(x, y);
                    if (diff == null || diff % 3 != 0) {
                        lies++;
                    }
                } else {
                    wuf.union(x, y, 0); // x和y同类，差值为0
                }
            } else {
                // x吃y，即x是y的捕食者
                // x到y的关系应该是1（x被y吃？不对）
                // 重新定义：weight[y] - weight[x] = 1 表示 y 吃 x
                // 所以 x 吃 y 意味着 y 被 x 吃，即 weight[x] - weight[y] = 1
                // 即 weight[y] - weight[x] = -1 ≡ 2 (mod 3)
                if (wuf.connected(x, y)) {
                    Long diff = wuf.queryDifference(x, y);
                    // x吃y <=> (weight[y] - weight[x]) mod 3 == 2
                    if (diff == null || Math.floorMod(diff, 3) != 2) {
                        lies++;
                    }
                } else {
                    wuf.union(x, y, -2); // y - x = -2 ≡ 1 (mod 3)? 需要重新确认
                    // x吃y：在x的视角，y是它的食物
                    // 设关系值：0=同类，1=x吃y，2=y吃x
                    // x吃y => relation(x,y) = 1
                    // 用带权：weight[y] - weight[x] = ?
                    // 如果 weight[y] - weight[x] = 1，表示y的关系比x高1
                    // 0->1->2->0 循环：同类(0), 吃(1), 被吃(2)
                    // x吃y：y相对于x的状态是"被吃" = 2？还是"吃"=1？
                    // 设weight[y] - weight[x] = 1 表示 x吃y
                    wuf.union(x, y, 1);
                }
            }
        }
        return lies;
    }
}

/**
 * 模3带权并查集（专用于食物链等循环关系）
 */
class WeightedUnionFindMod3 {
    private int[] parent;
    private int[] rank;
    private int[] rel; // rel[i]表示i到parent[i]的关系（模3）

    public WeightedUnionFindMod3(int n) {
        parent = new int[n];
        rank = new int[n];
        rel = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            int root = find(parent[x]);
            rel[x] = (rel[x] + rel[parent[x]]) % 3;
            parent[x] = root;
        }
        return parent[x];
    }

    public boolean union(int x, int y, int relation) {
        int rx = find(x);
        int ry = find(y);
        int dx = rel[x]; // x到rx的关系
        int dy = rel[y]; // y到ry的关系

        if (rx == ry) {
            // 检查一致性：(dy - dx) mod 3 应该等于 relation
            return ((dy - dx) % 3 + 3) % 3 == relation;
        }

        // 将ry挂到rx下
        // 需要：合并后 (new_dy - new_dx) % 3 == relation
        // new_dx = dx, new_dy = dy + delta
        // (dy + delta - dx) % 3 == relation
        // delta = (relation + dx - dy) % 3
        parent[ry] = rx;
        rel[ry] = ((relation + dx - dy) % 3 + 3) % 3;
        rank[rx] += rank[ry];
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public Integer queryDifference(int x, int y) {
        if (find(x) != find(y)) return null;
        return ((rel[y] - rel[x]) % 3 + 3) % 3;
    }
}

/**
 * 经典应用2：差分约束系统求解
 * 给定一组不等式 x_i - x_j <= c_k，判断是否有解，并求出一组可行解
 */
class DifferenceConstraintsSolver {

    static class Edge {
        int from, to;
        int weight;
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * 使用SPFA求解差分约束系统
     * 将 x_i - x_j <= c 转化为 j -> i 的边，权重为c
     * 添加超级源点0，到所有节点的边权重为0
     * 如果存在负环，则系统无解
     */
    public static boolean solve(int n, List<Edge> constraints, long[] solution) {
        ArrayList<Edge>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 添加约束边
        for (Edge e : constraints) {
            graph[e.from].add(e);
        }

        // 添加超级源点0
        for (int i = 1; i <= n; i++) {
            graph[0].add(new Edge(0, i, 0));
        }

        // SPFA求最短路
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;

        int[] count = new int[n + 1]; // 入队次数
        boolean[] inQueue = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        inQueue[0] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (Edge e : graph[u]) {
                if (dist[u] != Long.MAX_VALUE && dist[e.to] > dist[u] + e.weight) {
                    dist[e.to] = dist[u] + e.weight;
                    if (!inQueue[e.to]) {
                        queue.add(e.to);
                        inQueue[e.to] = true;
                        count[e.to]++;
                        // 如果入队次数超过n次，存在负环，无解
                        if (count[e.to] > n) {
                            return false;
                        }
                    }
                }
            }
        }

        // dist[i] 即为 x_i 的一个可行解
        System.arraycopy(dist, 1, solution, 0, n);
        return true;
    }

    public static void main(String[] args) {
        // 示例：x1 - x2 <= 3, x2 - x3 <= -2, x1 - x3 <= 4
        List<Edge> constraints = new ArrayList<>();
        constraints.add(new Edge(2, 1, 3));  // x1 - x2 <= 3
        constraints.add(new Edge(3, 2, -2)); // x2 - x3 <= -2
        constraints.add(new Edge(3, 1, 4));  // x1 - x3 <= 4

        long[] solution = new long[3];
        boolean hasSolution = solve(3, constraints, solution);

        System.out.println("差分约束系统:");
        System.out.println("  x1 - x2 <= 3");
        System.out.println("  x2 - x3 <= -2");
        System.out.println("  x1 - x3 <= 4");
        System.out.println("是否有解: " + hasSolution);
        if (hasSolution) {
            System.out.printf("可行解: x1=%d, x2=%d, x3=%d%n", solution[0], solution[1], solution[2]);
        }
    }
}

/**
 * 综合测试
 */
public class WeightedUnionFindDemo {
    public static void main(String[] args) {
        // 测试1：基础带权并查集
        System.out.println("=== 带权并查集基础测试 ===");
        WeightedUnionFind wuf = new WeightedUnionFind(5);

        // 建立关系：value[1] - value[0] = 5
        wuf.union(0, 1, 5);
        // 建立关系：value[2] - value[1] = 3
        wuf.union(1, 2, 3);
        // 建立关系：value[3] - value[0] = 10
        wuf.union(0, 3, 10);

        System.out.println("0和2的差值: " + wuf.queryDifference(0, 2)); // 应该是8
        System.out.println("0和3的差值: " + wuf.queryDifference(0, 3)); // 应该是10
        System.out.println("连通分量数: " + wuf.getCount());

        // 测试矛盾关系
        System.out.println("\n矛盾关系测试:");
        boolean ok = wuf.union(0, 2, 100); // 0和2的差值已知是8，不能是100
        System.out.println("尝试设置差值为100: " + ok); // 应为false

        // 测试2：食物链
        System.out.println("\n=== 食物链问题测试 ===");
        int[][] statements = {
            {1, 1, 2}, // 1和2是同类
            {1, 2, 3}, // 2和3是同类
            {2, 1, 3}, // 1吃3 —— 这是假话，因为1和3是同类
            {2, 2, 3}, // 2吃3 —— 这是真话
        };
        int lies = FoodChainSolver.solve(3, statements);
        System.out.println("假话数量: " + lies); // 应为1

        // 测试3：差分约束
        System.out.println("\n=== 差分约束测试 ===");
        DifferenceConstraintsSolver.main(args);
    }
}

算法复杂度分析

关键知识点总结

1. 权值的物理意义：带权并查集中weight[i]的物理意义取决于具体问题。在食物链问题中，它表示物种间的捕食关系（模3）；在差值问题中，它表示节点值的差。

2. 路径压缩的权值传递：当节点x的父节点被压缩到根时，x的权值需要累加父节点到根的权值。这是带权并查集与普通并查集最核心的区别。

3. 合并时的权值推导：合并两个集合时，需要推导出根节点之间的权值关系。设要将rootY挂到rootX下，通过已知的weight[x]、weight[y]和目标关系w，可以解出rootY到rootX的权值。

4. 扩展域技巧：对于多状态关系（如食物链的3种关系），可以为每个实体创建多个节点分别代表不同状态，或者使用模运算将关系压缩到权值中。

5. 应用场景：带权并查集广泛应用于食物链判定、银河英雄传说（序列维护）、二维平面上的曼哈顿距离约束、差分约束的特殊形式等问题。