LeetCode LCR 118. 冗余连接

约 6 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 广度优先搜索 LCR 图 并查集

题目描述

✅ LCR 118. 冗余连接

image-20260929004738073

image-20260929004738074

题意分析

输入是在一棵 n 个节点的无向树上增加一条边得到的连通图。删除某条边后需要恢复为树；如果有多条边可以删除，返回在输入中出现最靠后的那条。节点编号从 1 到 n，边数也恰好是 n。

解法：并查集按输入顺序判环

核心思路

[!blue]

树中任意两点已有唯一的连接路径，再加一条边会形成唯一一个环。环上的任意边都可以删除而恢复为树；不在环上的边连接着树的分支，删除会使图断开。因此目标是唯一环中在输入里出现最晚的边。

按输入顺序逐条加入边，用并查集维护已加入边的连通性。若新边两端根不同，就合并两个连通分量，不会成环；若两端根相同，说明之前已经有一条路径连接它们，新边加上这条路径正好闭合成环。

在唯一环的最后一条边到来前，环上的边尚未收齐，不可能已经形成别的环。最后一条到来时，其余环边已连通它的两端，于是它恰好是第一次遇到的同根边。直接返回它，就同时满足“删除后为树”和“输入位置最靠后”，不必保存所有候选。

初始每个节点独立成组，数组开到 n+1 以覆盖编号 n。查找时压缩父路径，合并时只连接两个集合根并按秩控制树形；这些操作只维护连通分量，不需要记录环的具体路径。

解题步骤

  1. 令 n = edges.length，建立长度为 n+1 的父节点和秩数组，初始化编号 1 到 n。
  2. 按输入原顺序读取一条边，查询两个端点的根。
  3. 同根则返回当前边；不同根则按秩合并两个集合。
  4. 继续处理后续边。题目保证存在冗余边，因此一定会在循环中返回答案。

代码实现

// 按输入顺序合并边；首次连接已连通两点的边就是冗余边。
class Solution {
    private int[] parent;
    private int[] rank;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;

        parent = new int[n + 1];
        rank = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];

            if (find684(u) == find684(v)) {
                return e;
            }

            union684(u, v);
        }

        return new int[0];
    }

    private int find684(int x) {
        if (parent[x] != x) {
            parent[x] = find684(parent[x]);
        }

        return parent[x];
    }

    private void union684(int a, int b) {
        int pa = find684(a);
        int pb = find684(b);

        if (pa == pb) {
            return;
        }

        if (rank[pa] < rank[pb]) {
            parent[pa] = pb;
        } else if (rank[pa] > rank[pb]) {
            parent[pb] = pa;
        } else {
            parent[pb] = pa;
            rank[pa]++;
        }
    }
}

// 按输入顺序合并边；首次连接已连通两点的边就是冗余边。
func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    rank := make([]int, n+1)

    for i := 1; i <= n; i++ {
        parent[i] = i
    }

    var find func(x int) int
    find = func(x int) int {
        if parent[x] != x {
            // 路径压缩：后续查找直接到达当前连通分量的根。
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) bool {
        rootX, rootY := find(x), find(y)
        if rootX == rootY {
            return false
        }

        // 按秩合并，避免并查集树退化成链。
        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else {
            parent[rootY] = rootX
            rank[rootX]++
        }
        return true
    }

    for _, edge := range edges {
        x, y := edge[0], edge[1]

        if !union(x, y) {
            return edge
        }
    }

    return nil
}

复杂度分析

  • 时间复杂度：$O(n\alpha(n))$，每条边执行常数次并查集操作，路径压缩与按秩合并的摊还成本为 $O(\alpha(n))$。
  • 空间复杂度：$O(n)$，保存父节点与秩；递归查找的栈空间不超过此量级。

关键点总结

[!green]

  • 无向边连接两个已连通的端点时才会成环，判断应比较集合根。
  • 环上有多条可删除边，顺序扫描首次闭环找到的是其中输入位置最晚的一条。
  • 此结论依赖题目保证整图只有一个环，不能直接推广到任意多环图的最后一条候选。
  • 节点从 1 编号，数组大小取边数加一，不能漏掉最大编号。

易错点总结

[!yellow]

  • 节点从 1 编号，父数组长度和初始化范围都覆盖 n。
  • 先查两端是否同根，再决定是否合并；直接比较中间父指针不等于比较集合根。
  • 按输入顺序遇到闭合唯一环的边即返回，它满足要求的靠后边规则，不按节点编号挑选。

相似题目

题目 难度 关联与区别
261. 以图判树 中等 同样判断无向图中的环和树结构，本题按边顺序找到使既有连通分量形成环的那条边。
685. 冗余连接 II 困难 加入有向关系后还要处理入度为2，不能只用无向并查集找环。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/52054082
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！