LeetCode 684. 冗余连接

2022-10-07 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 684. 冗余连接

题意分析

要什么：给一个由 n 个节点和 n 条无向边构成的图，它是在一棵 n 个节点的树上多加了一条边得到的。找出这条多余的边并返回；若有多个答案，返回在输入中出现最靠后的那一条。
约束透露的信号：n 个节点配 n 条边、且原本是树，这意味着整个图连通且恰好含有一个环——多出的那一条边必然是环上的边。「返回最后出现的那条」进一步说明：按输入顺序处理，第一条让图产生环的边就是答案，因为环上更早的边在被处理时还没有成环。题目关心的是「两个端点是否已经连通」而不是环的具体形状，这正是并查集的强项：它只回答连通性，不保存路径。
边界：节点编号从 1 开始而不是 0，数组要开 n + 1 长度；边是无向的，(u, v) 与 (v, u) 等价；题目保证一定有解，所以循环结束后的返回语句只是形式上的兜底；不会出现自环或重复边之外的非法输入。

解法：并查集判环

核心思路

暴力做法是逐条加边，每加一条就用 DFS 或 BFS 检查全图是否出现环，或者在加边前先搜索 u 到 v 是否已经连通。正确，但每次搜索都是 $O(n)$，总代价 $O(n^2)$，而且要反复重建邻接表。
瓶颈在于：判断「u 和 v 是否已经连通」被当成了一次全新的图搜索，而这个信息其实可以增量维护——每加一条边，连通关系只会合并，不会拆分。
关键观察是把「树」的性质翻译成连通性语言：一条边 (u, v) 会形成环，当且仅当加入它之前 u 与 v 已经处在同一个连通分量中。因为它们已连通说明存在一条 u 到 v 的路径，再补上这条直连边就闭合成环。
于是要维护的状态就是每个节点所属连通分量的代表元（根），不变量是：处理完前 i 条边后，并查集中任意两点同根，当且仅当它们在这 i 条边构成的图中连通。按输入顺序扫边，第一次遇到「两端已同根」的边就返回，它必然是环上出现最晚的那条——因为环上的其余边都在它之前被处理，处理时尚未闭环。
为了让每次查询接近常数时间，并查集要配两项优化：查找时做路径压缩（把沿途节点直接挂到根上），合并时做按秩合并（把矮树挂到高树下，避免树被拉成链）。

解题步骤

开长度 n + 1 的 parent 与 rank 数组，令 parent[i] = i。为什么是 n + 1：节点编号是 1 到 n，下标 0 空置；开 n 会在访问节点 n 时越界。为什么初始各自为根：起始时没有任何边，每个节点自成一个连通分量。为什么 n 可以直接取边数：树有 n-1 条边，加一条后恰好 n 条，所以边数等于节点数。

按输入顺序遍历每条边 (u, v)，先分别求两端的根。为什么必须按输入顺序：题目要求返回最后出现的答案边，顺序扫描 + 首次命中即返回，天然满足这个要求；打乱顺序会返回环上的另一条边。

若两根相同，立刻返回这条边。为什么可以立刻返回：图中只有一个环，第一次出现「加边前已连通」的时刻只会发生一次，此时这条边就是唯一答案。

否则合并两个分量，按秩把矮的挂到高的下面，秩相等时任选一个当根并把它的秩加一。为什么要按秩：不加控制的合并可能把树退化成一条 n 长的链，单次查找变成 $O(n)$；按秩合并保证树高是对数级。为什么秩不需要在其它情况下更新：只有两棵等高的树合并时整体高度才会加一，其余情况新根的高度不变。

查找函数递归到根并把沿途节点的父指针直接改写为根。为什么路径压缩不会破坏正确性：压缩只改变树的形态，不改变任何节点所属的集合，而我们关心的只有「根是谁」。

循环结束返回空。为什么这句永远不会执行：题目保证图中一定存在多余的边，写它只是为了让函数在语法上完整。

以 edges = [[1,2], [1,3], [2,3]] 走一遍。初始 parent = [_, 1, 2, 3]，rank 全 0。第一条 [1, 2]：find(1) = 1、find(2) = 2，不同根，秩相等故把 2 挂到 1 下并令 rank[1] = 1，此时分量为 {1, 2} 和 {3}。第二条 [1, 3]：find(1) = 1、find(3) = 3，不同根，rank[1] = 1 大于 rank[3] = 0，把 3 挂到 1 下，rank[1] 保持 1，此时三点同属一个分量。第三条 [2, 3]：find(2) 沿父指针到 1、find(3) 也到 1，两根相同——说明 2 和 3 之间早已通过节点 1 连通，再加这条边就闭合出环 1-2-3-1，于是返回 [2, 3]。这也印证了「返回最后出现的边」：环上的 [1,2] 和 [1,3] 在被处理时都还没成环，只有最后这条触发了判定。

代码实现

// 核心实现：并查集判环，维护必要状态并避免重复处理。
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 \cdot \alpha(n))$，其中 $\alpha$ 是反阿克曼函数，实际中不超过 5，可视为近似线性。凭什么：每条边做常数次 find 与至多一次 union，而路径压缩配合按秩合并把单次操作的均摊代价压到 $\alpha(n)$。

空间复杂度：$O(n)$。凭什么：parent 与 rank 两条长度 n + 1 的数组是全部额外开销；递归版 find 在路径压缩生效前最深为树高，按秩合并保证其为 $O(\log n)$。

关键点总结

「加边成环」等价于「两端已连通」，这是并查集判环的核心翻译。凡是题目在讨论无向图的环、连通块合并、等价类划分，先想并查集而不是搜索。注意这条等价只对无向图成立，有向图的环要用拓扑排序或颜色标记的 DFS。

顺序扫描 + 首次命中天然满足「返回最后出现的答案」这类要求。看到「若有多个答案返回最后 / 最先的那个」，先想能不能用扫描顺序把它变成免费的性质，而不是收集全部答案再排序。

并查集的两项优化要成对记牢：路径压缩让查找变扁，按秩（或按大小）合并防止树退化。只用其中一个也能过绝大多数题，但面试里被问到复杂度时必须说得出 $\alpha(n)$ 的来历。

编号从 1 开始是这题最常见的低级失误来源。凡是节点编号从 1 起的图论题，数组一律开 n + 1 并从 1 初始化，写完立刻检查一遍。

面试视角：说清「图恰好一个环」的来源（n 点 n 边且原为树），再给出并查集方案，最后主动提一句「本题也可以用 DFS 逐条加边判连通，代价 $O(n^2)$；数据大时并查集是唯一可行解」，并说明与「冗余连接 II」（有向图版）的差别在于要额外处理入度为 2 的节点。

易错点总结

错误写法：数组开成 new int[n]；用例 edges = [[1,2],[1,3],[2,3]] → n = 3，访问节点 3 时下标越界异常。

错误写法：初始化循环写成 for (int i = 0; i < n; i++) parent[i] = i；用例 edges = [[1,2],[1,3],[2,3]] → parent[3] 保持 0，节点 3 的根被算成 0，与其它分量错误地混为一体，第二条边就被误判为成环，返回 [1,3]。

错误写法：先合并再判断是否同根；用例任意输入 → 每条边合并后两端必然同根，判定恒为真，第一条边就被当成答案返回。

错误写法：判断时直接比较 parent[u] == parent[v] 而不是 find(u) == find(v)；用例 edges = [[1,2],[2,3],[1,3]] → 处理第三条边时 parent[1] 和 parent[3] 可能是不同的中间节点，误判为不连通并继续合并，最终返回空数组。

错误写法：find 中写成 return find(parent[x]) 却不回写 parent[x]；用例链式输入如 [[1,2],[2,3],[3,4],...] → 没有路径压缩，树退化成长链，单次查找 $O(n)$，大数据下超时。

错误写法：按秩合并时无论秩是否相等都执行 rank[root]++；用例大量边 → 秩失去「树高上界」的含义，合并方向变得随意，树高失控，性能退化。

错误写法：把边当有向处理，只合并 u -> v 方向并用「v 的父亲设为 u」而不经过 find；用例 edges = [[1,2],[3,2],[1,3]] → 直接覆盖 parent[2] 会丢失原有的合并关系，连通性统计出错，返回错误的边。

错误写法：遍历到成环边时不立即返回，而是记录下来继续扫；用例本题输入 → 因为只有一个环所以结果恰好相同，但一旦沿用到多环场景（如自定义变形题）就会返回最后一条成环边而非题意要求的那条，且白白多做工作。

错误写法：用 DFS 判环并返回「环上编号最大的边」；用例 edges = [[1,2],[2,3],[1,3]] → 环上三条边编号大小与输入顺序无关，返回的可能不是最后出现的那条，正确答案是 [1,3]。

错误写法：Go 版本里把 union 的返回值语义写反（合并成功返回 false）；用例任意输入 → 第一条边就被判为冗余，返回 [1,2]。

相似题目

题目	难度	考察点
547. 省份数量	中等	只统计合并后剩下几个分量，不涉及判环，输入是邻接矩阵而非边列表
990. 等式方程的可满足性	中等	要分两趟处理，先合并所有等式再逐条校验不等式，考察约束的先后顺序
721. 账户合并	中等	合并对象是字符串，需要先做编号映射，合并后还要按根收集并排序输出
839. 相似字符串组	困难	边不是给定的而要靠两两判定相似性现场生成，瓶颈从合并转移到建边