并查集（Disjoint Set Union, DSU）

MrHe··12 min read

并查集（Disjoint Set Union, DSU）是一种非常有用的数据结构，主要用来处理一些不相交集合的合并及查询问题。听起来很抽象，但其实核心就两个操作：

  1. find：查找一个元素属于哪个集合（通常通过返回该集合的代表元素，也就是根节点）。

  2. union：将两个元素所在的集合合并成一个集合。

为了让find操作更快，我们通常会加上一个“路径压缩”的优化。为了让合并后的树结构更平衡，会加上“按秩合并”或“按大小合并”的优化。

10.2 一维并查集的应用算法设计

10.2.1 以图判树

问题描述

给定从 0 到 n-1 标号的 n 个节点，和一个无向边列表（每条边以节点对的形式给出），请编写一个函数用来判断这些边是否能够构成一棵有效的树。

示例 1: 输入: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]] 输出: true

示例 2: 输入: n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] 输出: false

注意：你可以假设给定的边列表不包含重复的边。由于所有边都是无向边，[0,1] 和 [1,0] 是相同的，因此不会同时出现在边列表中。

思路分析

要判断一个图是不是一棵树，需要满足两个条件：

  1. 连通性：图中的所有节点必须是连通的，不能有孤立的节点或多个连通分量。

  2. 无环：图中不能存在环。

再深入想一下，对于一个有 n 个节点的图，如果它满足下面两个条件中的任意一个，就能被证明是一棵树：

  • 该图是连通的，并且有 n-1 条边。

  • 该图是无环的，并且有 n-1 条边。

所以，我们的解题思路就清晰了。

解法一：DFS/BFS 遍历

这个思路很直观。首先，检查边的数量是否等于 n-1。如果不是，直接返回 false。如果边的数量是 n-1，那么我们只需要再判断图是否是连通的就行了。

怎么判断连通性？从任意一个节点（比如节点 0）开始进行深度优先搜索（DFS）或广度优先搜索（BFS），看看能不能访问到所有的 n 个节点。如果可以，说明图是连通的。

  1. 构建邻接表来表示图。

  2. 从节点 0 开始 DFS/BFS，用一个 visited 数组记录访问过的节点。

  3. 遍历结束后，统计 visited 数组中被标记为 true 的节点数量。

  4. 如果数量等于 n，并且边的数量是 n-1，那么这就是一棵有效的树。

代码实现 (DFS)

import java.util.ArrayList;
import java.util.List;

class Solution1 {
    public boolean validTree(int n, int[][] edges) {
        // 条件1: n个节点的树，必须有 n-1 条边
        if (edges.length != n - 1) {
            return false;
        }

        // 构建邻接表
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }

        // DFS 遍历，判断连通性
        boolean[] visited = new boolean[n];
        dfs(0, adjacencyList, visited);

        // 检查是否所有节点都被访问到
        int count = 0;
        for (boolean v : visited) {
            if (v) {
                count++;
            }
        }
        return count == n;
    }

    private void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
        if (visited[u]) {
            return;
        }
        visited[u] = true;
        for (int v : adj.get(u)) {
            dfs(v, adj, visited);
        }
    }
}

解法二：并查集

换个角度想，我们关注“环”的判断。在遍历边的过程中，如果一条边的两个端点已经属于同一个连通分量了，那么再加入这条边，必然会形成一个环。

这不就是并查集的经典应用场景吗？

  1. 初始化一个并查集，包含 n 个节点，每个节点各自是一个集合。

  2. 遍历 edges 数组中的每一条边 (u, v)。

  3. 对于每一条边，用 find 操作判断 u 和 v 是否已经连通。

    • 如果 find(u) == find(v)，说明它们在加入这条边之前就已经连通，现在加入这条边就会形成环。直接返回 false。

    • 如果 find(u) != find(v)，说明它们不连通，这条边是安全的。我们执行 union(u, v)，将它们合并到同一个集合中。

  4. 遍历完所有边都没有发现环，说明图是无环的。此时我们还需要判断图是否是连通的。

  5. 怎么用并查集判断连通性？很简单，如果最终只有一个连通分量（一个集合），那整个图就是连通的。我们可以通过一个计数器，初始为 n，每次成功 union 后减一。最后判断计数器是否为 1。

综合一下，其实就是：

  1. 遍历边，用并查集判断环。若有环，则不是树。

  2. 遍历完后，判断最终的连通分量数量是否为 1。

代码实现 (并查集)

class Solution2 {
    public boolean validTree(int n, int[][] edges) {
        // 初始化并查集
        UnionFind uf = new UnionFind(n);

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // 如果两个节点已经属于同一个集合，再加边就会形成环
            if (uf.find(u) == uf.find(v)) {
                return false;
            }
            // 否则，合并这两个集合
            uf.union(u, v);
        }

        // 最后，判断是否只有一个连通分量
        // 如果 n 个节点，有 n-1 条边，且无环，那必然是连通的。
        // 所以，可以简化为判断边的数量
        return edges.length == n - 1;
    }

    class UnionFind {
        private int[] parent;
        // (可选) 用于按大小合并的优化
        private int[] size;
        private int count; // 记录连通分量的数量

        public UnionFind(int n) {
            this.count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                // 路径压缩
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }

            // 按大小合并（小的合并到大的）
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
            count--;
        }

        public int getCount() {
            return count;
        }
    }
}

注意，在并查集的解法里，如果已经判断完无环，那么只要边的数量是 n-1，就一定能保证图是连通的。所以最后可以直接判断 edges.length == n - 1。

10.2.2 无向图中连通分量的数目

问题描述

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表，请计算无向图中连通分量的数目。

示例 1: 输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]] 输出: 2

示例 2: 输入: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]] 输出: 1

思路分析

这道题简直就是为并查集量身定做的。连通分量的数量，不就是问最后图里有多少个独立的“圈子”或者“帮派”嘛。

解法一：DFS/BFS

这个方法也很直观。我们遍历每一个节点，如果这个节点还没被访问过，就说明发现了一个新的连通分量。然后从这个节点开始进行 DFS 或 BFS，把所有能访问到的节点都标记为已访问。

  1. 初始化一个 visited 数组，所有元素都为 false。

  2. 初始化连通分量计数器 count = 0。

  3. 从 i = 0到 n-1 遍历所有节点。

  4. 如果 visited[i] 是 false，说明节点 i 属于一个新的、尚未探索的连通分量。

    • count 加一。

    • 从节点 i 开始执行一次 DFS 或 BFS，将所有与之相连的节点标记为已访问。

  5. 遍历结束后，count 的值就是连通分量的总数。

代码实现 (DFS)

import java.util.ArrayList;
import java.util.List;

class Solution1 {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                dfs(i, adj, visited);
            }
        }
        return count;
    }

    private void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
        if (visited[u]) {
            return;
        }
        visited[u] = true;
        for (int v : adj.get(u)) {
            dfs(v, adj, visited);
        }
    }
}

解法二：并查集

并查集的思路更加直接。

  1. 初始化一个并查集，包含 n 个节点。此时，每个节点都是一个独立的连通分量，所以总数是 n。

  2. 遍历 edges 数组中的每一条边 (u, v)。

  3. 对于每一条边，union(u, v)。

    • 在 union 操作内部，如果 u 和 v 的根节点不同，说明这条边连接了两个原本不相连的连通分量，那么总的连通分量数量就应该减一。

  4. 遍历完所有边之后，并查集中记录的连通分量数量就是最终答案。

代码实现 (并查集)

class Solution2 {
    public int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.getCount();
    }

    class UnionFind {
        private int[] parent;
        private int count; // 核心：记录连通分量的数量

        public UnionFind(int n) {
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            if (p != parent[p]) {
                parent[p] = find(parent[p]); // 路径压缩
            }
            return parent[p];
        }

        // union 操作返回 boolean 值，表示是否真的发生了合并
        public boolean union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return false;
            }
            parent[rootP] = rootQ;
            count--; // 只有在真正合并时才减少计数
            return true;
        }

        public int getCount() {
            return count;
        }
    }
}

这个题目，并查集的解法和它的设计初衷完美契合，代码也更简洁。

10.2.3 冗余连接

问题描述

树可以看成是一个连通且无环的无向图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息以长度为 n 的二维数组 edges 表示，edges[i] = [ui, vi] 表示图中存在一条边连接 ui 和 vi。 请找出一条可以删去的边，使得结果图是一个有着 n 个节点的树。如果有多个答案，则返回 edges 中最后出现的边。

示例 1： 输入: edges = [[1,2],[1,3],[2,3]] 输出: [2,3]

示例 2： 输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] 输出: [1,4]

思路分析

题目的意思是，给定的图是在一棵树的基础上多加了一条边，这条多余的边导致了图中出现了一个环。我们要做的，就是找出这条“惹事”的边。

解法一：DFS/BFS (每次都判断环)

这个思路有点暴力。我们按顺序处理每一条边，动态地构建图。对于每一条新边 (u, v)，我们先不把它加入图，而是检查一下当前图中 u 和 v 是否已经连通。

  1. 建一个空的邻接表。

  2. 遍历 edges 数组中的每一条边 (u, v)。

  3. 在加入这条边之前，用 DFS 或 BFS 从 u 出发，看是否能到达 v。

    • 如果能到达，说明 u 和 v 已经连通了，这条边 (u, v) 就是多余的，它造成了环。因为题目要求返回最后出现的答案，我们用一个变量记录下这条边，然后继续遍历。

    • 如果不能到达，说明这条边是安全的，将它加入邻接表中（u->v, v->u）。

  4. 遍历结束后，最后记录的那条冗余边就是答案。

这个方法每次判断连通性都需要一次图的遍历，效率不高。

代码实现 (DFS)

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution1 {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<List<Integer>> adj = new ArrayList<>();
        // 节点编号从1到n，所以我们创建 n+1 大小的列表
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        int[] result = null;
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            // 在添加这条边之前，检查 u 和 v 是否已经连通
            Set<Integer> visited = new HashSet<>();
            if (canReach(u, v, adj, visited)) {
                result = edge; // 找到一条冗余边，更新答案
            } else {
                // 如果不连通，安全地添加这条边
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }
        return result;
    }

    // DFS 判断 start 能否到达 end
    private boolean canReach(int start, int end, List<List<Integer>> adj, Set<Integer> visited) {
        if (start == end) {
            return true;
        }
        visited.add(start);
        for (int neighbor : adj.get(start)) {
            if (!visited.contains(neighbor)) {
                if (canReach(neighbor, end, adj, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}

解法二：并查集

这又是并查集的拿手好戏。判断“两个节点是否已经连通”，这正是 find 操作的意义。

  1. 初始化一个并查集，节点数量为 n（注意题目节点从1到n，并查集数组大小要 n+1）。

  2. 遍历 edges 数组中的每一条边 (u, v)。

  3. 对于每一条边，判断 u 和 v 的根节点是否相同。

    • 如果 find(u) == find(v)，说明在加入这条边之前，u 和 v 已经通过其他路径连通了。现在再加这条边，必然形成环。这条边就是我们要找的冗余连接。由于题目要求返回最后出现的，我们直接返回这条边即可（或者说，我们找到的第一个形成环的边，因为后面的边在题目设定下都是'必须'的）。等一下，题目要求返回 最后 出现的。所以我们不能找到第一个就返回，而是应该继续遍历，用一个变量记录下最后找到的那个。

    • 如果 find(u) != find(v)，说明它们还不连通，union(u, v)。

  4. 遍历完之后，变量里存的就是答案。

代码实现 (并查集)

class Solution2 {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        // 节点编号 1 到 n，所以并查集大小为 n+1
        UnionFind uf = new UnionFind(n + 1);

        int[] result = null;
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // 如果 u 和 v 已经在同一个集合，说明这条边是冗余的
            if (uf.find(u) == uf.find(v)) {
                result = edge; // 更新答案
            } else {
                uf.union(u, v);
            }
        }
        return result;
    }

    class UnionFind {
        private int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            if (p != parent[p]) {
                parent[p] = find(parent[p]);
            }
            return parent[p];
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                parent[rootP] = rootQ;
            }
        }
    }
}

你看，用并查集来处理，代码逻辑非常清晰，效率也高得多。

由于篇幅原因，后面的题目我会延续这个风格，快速切入核心思路和解法。如果你对某个具体细节有疑问，随时可以提。我先继续把剩下的题目讲完。

10.3 二维并查集

并查集本身是一维结构，怎么处理二维网格问题呢？很简单，降维打击！把二维坐标 (r, c) 映射成一维索引 index = r * cols + c。这样，二维网格里的每个点就对应了并查集里的一个元素，邻居关系就可以通过 union 操作来建立了。

10.3.1 岛屿数量

问题描述

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。

示例: 输入: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出: 1

思路分析

这道题是图遍历的经典入门题。

解法一：DFS/BFS

  1. 遍历整个网格。

  2. 遇到一个 '1'，并且这个 '1' 没被访问过，说明我们发现了一个新岛屿，岛屿数量加一。

  3. 从这个 '1' 开始，进行 DFS 或 BFS，把所有与之相连的 '1'（整个岛屿）都找到，并标记为已访问（比如，可以把 '1' 直接改成 '2' 或 '0'，来避免使用额外的 visited 数组）。

  4. 继续遍历网格，直到所有格子都被检查过。

代码实现 (DFS)

class Solution1 {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
            return;
        }

        // 标记为已访问，防止重复计数
        grid[r][c] = '0';

        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

解法二：并查集

用并查集怎么做？

  1. 初始化。

    • 计算网格中所有 '1' 的数量，这个是初始的岛屿数量（每个 '1' 都先看作一个小岛）。

    • 创建一个并查集，大小为 rows * cols。

  2. 遍历网格。

  3. 当遇到一个 '1' 在位置 (r, c) 时，我们看它的相邻位置（比如，下方和右方，避免重复检查）。

  4. 如果相邻位置 (nr, nc) 也是 '1'，说明这两个小岛其实是连在一起的。我们就执行 union(r * cols + c, nr * cols + nc)。

  5. 在 union 操作中，如果成功地合并了两个不同的集合，那么总的岛屿数量就应该减一。

  6. 遍历结束后，剩下的岛屿数量就是答案。

代码实现 (并查集)

class Solution2 {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        UnionFind uf = new UnionFind(grid);

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0'; // 避免重复访问，这里也可以用 visited 数组
                    // 向下合并
                    if (r + 1 < rows && grid[r+1][c] == '1') {
                        uf.union(r * cols + c, (r + 1) * cols + c);
                    }
                    // 向右合并
                    if (c + 1 < cols && grid[r][c+1] == '1') {
                        uf.union(r * cols + c, r * cols + (c + 1));
                    }
                }
            }
        }
        // 不能直接返回 uf.getCount()，因为水域('0')也被初始化了
        // 正确的做法是在 UnionFind 内部初始化 count 时只计算 '1' 的数量
        return uf.getCount();
    }

    class UnionFind {
        private int[] parent;
        private int count;

        public UnionFind(char[][] grid) {
            int rows = grid.length;
            int cols = grid[0].length;
            count = 0;
            parent = new int[rows * cols];
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == '1') {
                        int id = r * cols + c;
                        parent[id] = id;
                        count++;
                    }
                }
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                parent[rootP] = rootQ;
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }
}

10.4 带权并查集

有时候，我们不仅关心元素之间的连通关系，还想知道它们之间的某种量化关系（比如距离、倍数、差值等）。这时就要给并查集的边附上“权重”，这就是带权并查集。

核心思想是在 parent 数组之外，再维护一个 weight 数组。weight[i] 通常记录节点 i 到其父节点 parent[i] 的关系值。在路径压缩和合并操作中，需要同步更新这个权重。

10.4.4 除法求值

问题描述

给你一个变量对数组 equations 和一个实数值数组 values，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i]。每个 Ai 或 Bi 是一个表示变量的字符串。

另给你一个查询数组 queries，其中 queries[j] = [Cj, Dj] 表示第 j 个查询，请你计算 Cj / Dj 的结果。

返回所有查询的结果。如果某个查询的结果无法计算，则返回 -1.0。

示例 1： 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]

思路分析

这道题可以看作一个图问题。每个变量是一个节点，a / b = 2.0 就表示从 a到 b有条权重为 2.0 的有向边，同时从 b 到 a 有条权重为 1/2.0 的边。查询 a / c 的值，就是求图中从 a 到 c 的路径上所有边权的乘积。

解法一：图的 DFS/BFS

  1. 建图：用一个 HashMap<String, HashMap<String, Double>> 来存储图。map.get(a).get(b) 存储 a/b 的值。对于 a/b = v，我们需要存 a->b 的边权 v 和 b->a 的边权 1/v。

  2. 查询：对于每个查询 c / d，我们从节点 c 开始进行 DFS 或 BFS，目标是找到节点 d。在搜索过程中，我们需要累积路径上的权重乘积。

  3. 如果找到了路径，返回累积的乘积。如果搜索结束都没找到 d，或者 c、d 根本不在图中，返回 -1.0。为了防止在环里死循环，需要一个 visited 集合。

代码实现 (DFS)

import java.util.*;

class Solution1 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);
        double[] result = new double[queries.size()];

        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);
            result[i] = dfs(start, end, graph, new HashSet<>());
        }
        return result;
    }

    private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String u = equations.get(i).get(0);
            String v = equations.get(i).get(1);
            double value = values[i];

            graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, value);
            graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / value);
        }
        return graph;
    }

    private double dfs(String start, String end, Map<String, Map<String, Double>> graph, Set<String> visited) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            return -1.0;
        }
        if (start.equals(end)) {
            return 1.0;
        }

        visited.add(start);
        Map<String, Double> neighbors = graph.get(start);
        for (Map.Entry<String, Double> entry : neighbors.entrySet()) {
            String next = entry.getKey();
            if (!visited.contains(next)) {
                double subResult = dfs(next, end, graph, visited);
                if (subResult != -1.0) {
                    return entry.getValue() * subResult;
                }
            }
        }
        // visited.remove(start); // 如果需要回溯，但这里是单次查询，不需要
        return -1.0;
    }
}

解法二：带权并查集

这个解法更精妙。我们将每个变量看作一个节点。parent 数组存储父节点，weight 数组存储 node / parent[node] 的值。

  • find(x) 操作：在查找根节点的同时，进行路径压缩和权重更新。如果 parent[x] 不是根节点，我们递归调用 find(parent[x])。在递归返回后，我们知道了 parent[x] 的根节点 root，以及 parent[x] / root 的值。那么 x / root = (x / parent[x]) * (parent[x] / root)。我们更新 weight[x] 为这个新值，并将 parent[x] 直接指向 root。

  • union(x, y, value) 操作: value 代表 x / y 的值。我们先找到 x的根 rootX 和 y 的根 rootY。此时我们已知 x / rootX 和 y / rootY 的值。我们要合并 rootX 到 rootY，即 parent[rootX] = rootY。那 weight[rootX] (即 rootX / rootY) 应该是什么呢？ rootX / rootY = (rootX / x) * (x / y) * (y / rootY)。 其中 rootX / x 是 1 / weight[x]，x / y是给定的 value，y / rootY 是 weight[y]。 所以，weight[rootX] = (value * weight[y]) / weight[x]。

  • 查询 c / d：如果 c 和 d 属于同一个集合（即 find(c) == find(d)），那么 c / d = (c / root) / (d / root) = weight[c] / weight[d]。否则，无法计算。

代码实现 (带权并查集)

import java.util.*;

class Solution2 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 预处理，给所有字符串变量一个整数ID
        UnionFind uf = new UnionFind();
        for (int i = 0; i < equations.size(); i++) {
            String u = equations.get(i).get(0);
            String v = equations.get(i).get(1);
            double value = values[i];
            uf.union(u, v, value);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String u = queries.get(i).get(0);
            String v = queries.get(i).get(1);

            if (!uf.parent.containsKey(u) || !uf.parent.containsKey(v)) {
                result[i] = -1.0;
                continue;
            }

            String rootU = uf.find(u);
            String rootV = uf.find(v);

            if (!rootU.equals(rootV)) {
                result[i] = -1.0;
            } else {
                result[i] = uf.weight.get(u) / uf.weight.get(v);
            }
        }
        return result;
    }

    class UnionFind {
        // parent.get(x) -> x的父节点
        Map<String, String> parent = new HashMap<>();
        // weight.get(x) -> x / parent.get(x) 的值
        Map<String, Double> weight = new HashMap<>();

        // find 方法返回的是根节点
        public String find(String s) {
            if (!parent.containsKey(s)) {
                parent.put(s, s);
                weight.put(s, 1.0);
            }
            if (!s.equals(parent.get(s))) {
                String originalParent = parent.get(s);
                String root = find(originalParent);
                parent.put(s, root);
                // 更新权重: s/root = (s/originalParent) * (originalParent/root)
                weight.put(s, weight.get(s) * weight.get(originalParent));
            }
            return parent.get(s);
        }

        // x / y = value
        public void union(String x, String y, double value) {
            String rootX = find(x);
            String rootY = find(y);
            if (!rootX.equals(rootY)) {
                parent.put(rootX, rootY);
                // 推导: rootX/rootY = (rootX/x) * (x/y) * (y/rootY)
                // weight(rootX) = (1/weight(x)) * value * weight(y)
                weight.put(rootX, (value * weight.get(y)) / weight.get(x));
            }
        }
    }
}

带权并查集在这个问题上，通过预处理所有 equations 构建了关系网络。之后每次查询都非常快，接近 O(1) 的复杂度（取决于路径压缩的效果），整体性能优于每次查询都要重新遍历的 DFS/BFS 方法。

  • #5bm25pl6zug