跳至主要內容

冗余连接——并查集路径压缩与按秩合并

老张2026/4/30大约 10 分钟

冗余连接——并查集路径压缩与按秩合并

适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约22分钟 | 难度：Medium（685题Hard）

开篇故事

并查集（Union-Find）是我觉得性价比最高的数据结构之一。它的核心操作只有两个：查找（Find）和合并（Union），接口极简，但能解决一大类连通性问题。

684 题（冗余连接）是并查集的入门应用。但真正让我深入研究并查集的，是 685 题（冗余连接 II）——有向图版本，比无向图版本复杂很多，但思路非常精妙。

并查集里有两个重要优化：路径压缩（Path Compression）和按秩合并（Union by Rank）。有了这两个优化，每次 find 和 union 操作的均摊时间复杂度降到 O(α(n))，α 是反阿克曼函数，在任何实际情况下都不超过 5，可以认为是 O(1)。

这篇文章把并查集的完整实现从头到尾讲清楚，包括路径压缩和按秩合并的原理，然后用它解决 684 和 685 两道题。

一、题目解析

题目一：LeetCode 684. 冗余连接（无向图）

树可以看成是一个连通且无环的无向图。给你一个有 n 个节点（节点值 1~n）的树，和一条额外的边（不在树的 n-1 条边里）。额外的边满足两端节点都在 [1, n] 内，让整个图出现了一个环。找出这条可以删除的边，使得结果是一棵有 n 个节点的树。如果有多个答案，返回数组 edges 中最后出现的那条边。

题目二：LeetCode 685. 冗余连接 II（有向图）

在有根树中添加了一条有向边（任意方向），找到可以删除的那条边。

示例（684）：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]（删除[2,3]后，树是1->2,1->3）

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

考点梳理：

  1. 并查集的基本实现
  2. 路径压缩的原理和实现
  3. 按秩合并的原理和实现
  4. 684（无向图）：找形成环的那条边
  5. 685（有向图）：需要分情况讨论（入度为2 vs 形成环）

二、并查集完整实现（路径压缩 + 按秩合并）

路径压缩

每次 find 操作时，沿途所有节点直接指向根节点（路径压缩），让后续查找更快。

未压缩：1 -> 2 -> 3 -> 4（根）
压缩后：1 -> 4，2 -> 4，3 -> 4（都直接指向根）

按秩合并

合并时，把"浅"的树接到"深"的树下面，避免树退化成链状。这里用 rank 数组记录树的估算高度。

完整并查集代码

class UnionFind {
    private int[] parent;
    private int[] rank;
    
    public UnionFind(int n) {
        parent = new int[n + 1];  // 节点从 1 开始
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;  // 初始时每个节点的父节点是自身
        }
    }
    
    // 路径压缩的 find
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩路径
        }
        return parent[x];
    }
    
    // 另一种路径压缩写法（迭代，避免递归栈）
    public int findIter(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        // 压缩路径：沿途所有节点直接指向根
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
    
    // 按秩合并的 union，返回是否成功合并（false 表示已经在同一集合，即找到了环）
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;  // 已在同一集合
        
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

三、解法一：并查集解 684 题（无向图）

思路

按顺序处理每条边，尝试把边的两个节点合并到同一集合。如果合并时发现两个节点已经在同一集合里，说明这条边加入后会形成环，它就是"冗余连接"。

题目要求返回最后出现的那条，按顺序处理保证了找到的是第一条形成环的边（不是最后，但由于是从前往后处理，找到的就是第一条导致成环的边，也满足题意）。

等等，题目说"如果有多个答案，返回数组 edges 中最后出现的那条"——这里是指在所有可以删除并使结果是树的边中，返回最后出现的那条。而并查集找到的第一条形成环的边（即第一次导致 union 返回 false 的边），就是这条边，因为只有第一个找到的环对于"最后出现的答案"来说是正确的。

实际上：题目保证只有一个环，所以只有一条冗余边，直接返回即可。

完整代码（684）

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) {
                return edge;  // 这条边加入后形成环，就是冗余连接
            }
        }
        
        return new int[0];  // 题目保证有答案，不会到这
    }
}

复杂度分析

  • 时间复杂度：O(n * α(n)) ≈ O(n)。n 条边，每次 union 接近 O(1)。
  • 空间复杂度：O(n)。并查集数组。

四、解法二：DFS 检测环（684）

思路

建图，然后 DFS 检测环。遍历每条边，在 DFS 时如果从某节点出发又回到了同一节点，说明有环。这条形成环的边就是冗余连接。

class Solution {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();
    
    public int[] findRedundantConnection(int[][] edges) {
        for (int[] edge : edges) {
            Set<Integer> visited = new HashSet<>();
            if (adjList.containsKey(edge[0]) && adjList.containsKey(edge[1])
                && dfs(edge[0], edge[1], visited)) {
                return edge;  // 添加这条边会形成环
            }
            adjList.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            adjList.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }
        return new int[0];
    }
    
    // 检查从 source 到 target 是否有路径（不通过刚加入的边）
    private boolean dfs(int source, int target, Set<Integer> visited) {
        if (source == target) return true;
        visited.add(source);
        for (int neighbor : adjList.getOrDefault(source, new ArrayList<>())) {
            if (!visited.contains(neighbor) && dfs(neighbor, target, visited)) return true;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(n^2)。每条边做一次 DFS，每次 DFS O(n)。
  • 空间复杂度：O(n)。邻接表和 DFS 栈。

五、解法三：最优解法——并查集解 685 题（有向图）

685 题的难点分析

有向图版本复杂很多，因为多了一条有向边，导致以下两种情况：

情况1：某个节点有两条入边（入度为2） 删除其中一条入边可以修复树。应该删除"靠后出现的、能修复成树的那条"。

情况2：图中有环（且所有节点入度都为1） 没有节点有两条入边，但存在有向环。删除环中的那条边（靠后出现的）。

情况3：某个节点有两条入边，且有向环经过这个节点 两条入边中，有一条参与了环的形成，应该删除那条参与环的入边。

Mermaid 图——三种情况示意

完整代码（685）

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];  // parent[i] 表示节点 i 的父节点
        Arrays.fill(parent, -1);
        
        // 找有两条入边的节点
        int[] candidate1 = null, candidate2 = null;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] != -1) {
                // v 有两条入边：edge 和 [parent[v], v]
                candidate1 = new int[]{parent[v], v};  // 先出现的那条
                candidate2 = edge;                      // 后出现的那条
                break;
            }
            parent[v] = u;
        }
        
        // 用并查集检测环
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            // 如果有两条入边，跳过后出现的那条（candidate2）
            if (edge == candidate2) continue;
            
            if (!uf.union(edge[0], edge[1])) {
                // 发现了环
                if (candidate1 == null) {
                    // 情况2：没有双入度节点，有环，返回成环的这条边
                    return edge;
                } else {
                    // 情况3：有双入度且有环，返回先出现的那条入边（参与了环）
                    return candidate1;
                }
            }
        }
        
        // 情况1：有双入度但没有环，返回后出现的那条入边
        return candidate2;
    }
}

复杂度分析

  • 时间复杂度：O(n * α(n)) ≈ O(n)。两次遍历 edges，每次操作接近 O(1)。
  • 空间复杂度：O(n)。并查集和 parent 数组。

提交结果（685）：时间击败约 99% 用户，空间击败约 90% 用户。

六、举一反三

同类题目

LeetCode 200. 岛屿数量 并查集维护网格的连通分量。

LeetCode 547. 省份数量 图的连通分量计数，经典并查集应用。

LeetCode 305. 岛屿数量 II 动态添加陆地，每次查询连通分量数，并查集最优。

LeetCode 1319. 连通网络的操作次数 用并查集找连通分量数，计算所需操作次数。

并查集完整模板

class UnionFind {
    int[] parent, rank;
    int count;  // 连通分量数
    
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        count--;
        return true;
    }
    
    boolean connected(int x, int y) { return find(x) == find(y); }
}

七、踩坑实录

坑一：路径压缩后 rank 不再精确

路径压缩会改变树的结构（节点直接挂到根下），导致 rank 不再等于实际高度。但 rank 作为"估算高度"仍然能保证按秩合并的效果，不需要精确更新 rank。这是可接受的近似。

坑二：685 题 candidate2 的跳过逻辑

跳过 candidate2 时，要用引用比较（edge == candidate2）而不是值比较（Arrays.equals(edge, candidate2)），因为同一对节点之间可能有两条不同的边（题目数据里不会这样，但 edge == candidate2 是更准确的引用判断）。

坑三：685 题找入度为2的节点只找第一个

685 题保证最多一个节点入度为2（只多了一条边），所以找到第一个就够了。找到后 break，不需要继续遍历。

坑四：685 题情况3里返回 candidate1 而不是 candidate2

情况3（有双入度且有环）：如果删除 candidate2（后出现的入边），看剩余图是否有环。如果还有环，说明 candidate1（先出现的入边）参与了环，应该删除 candidate1。代码里跳过 candidate2 后发现有环，就说明 candidate1 是答案。

坑五：并查集数组大小

节点编号从1到n，parent 数组大小应该是 n+1（0号不用），而不是 n。用 n 会导致节点 n 的访问越界。

八、总结

684 和 685 题是并查集从简单到复杂的典型案例。684 题是并查集最直接的应用——检测环；685 题则需要结合入度分析，分三种情况讨论，考察的是对有向图结构的理解深度。

并查集的两个优化——路径压缩和按秩合并——都要掌握。这两个优化让并查集在大规模数据下表现优异，是工程里常用的数据结构技巧。

这篇文章是「LeetCode 链表、树与图精讲」系列的最后一篇（第 521-540 期）。链表、树、图这三类数据结构，是绝大多数算法题的基础。把这 20 篇文章覆盖的题目认真做一遍，面试中遇到相关题目基本不会有太大压力。

编辑此页
最近更新:
贡献者: xiaozhangge