LeetCode 684. 冗余连接

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
深度优先搜索 广度优先搜索 图 并查集

题目描述

✅ 684. 冗余连接

image-20260929104532060

image-20260929104532174

题意分析

输入是一棵无向树再添加一条额外边得到的连通图，需要删除一条边恢复成树；若有多种选择，返回输入顺序最靠后的那条。

树中任意两点原本只有一条路径，加边以后形成唯一的环。删除环上的任意一条边都能恢复成树，删除环外边却会断开连通性，因此要找的是唯一环上最后出现的边。

解法：并查集判环

核心思路

[!blue]

按输入顺序处理边，用并查集维护已经加入的边所形成的连通分量。每个节点开始独立成组，find(x) 返回其代表根；两点的根相同，就表示已有一条路径把它们连起来。

对新边 (u,v)，如果两端根不同，加入这条边只会连接两个分量，不会成环，合并两个根即可。如果两端根相同，已有路径加上当前新边就会闭合一个环，当前边可以删除。

第一次发现成环就能满足“最后出现”的要求，是因为整个输入只有一个环。在该环最后一条边被处理之前，其余已扫描边不可能构成另一个环；最后一条环边到来时，其余环边已经构成连接它两个端点的路径，所以恰好在这里首次发现两端同根。检测到的正是环上输入位置最靠后的边，即使之后还有环外边，也无需继续扫描。

find 将沿途节点直接连接到根，压缩后续查找路径；合并时让低秩根接到高秩根下，只有秩相同时才增加保留根的秩。这些操作只改变集合的表示，不改变节点之间已经建立的连通关系。

解题步骤

  1. 题目中节点编号是 1..n，且边数为 n，建立长度为 n+1 的父节点和秩数组。
  2. 将每个节点的父节点初始化为自身。
  3. 按输入顺序读取边，先查找两端代表根。
  4. 根相同就立即返回当前边；根不同则按秩合并，并继续处理。
  5. 题目保证输入由树加一条边得到，因此一定会找到一次成环连接。

代码实现

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))$。最多扫描 n 条边，路径压缩与按秩合并使每次并查集操作的摊还时间为 $O(\alpha(n))$。
  • 空间复杂度：$O(n)$。父节点、秩数组及查找的递归栈都包含在这一上界内。

关键点总结

[!green]

  • 成环依据是两端已存在连通路径，不是两个节点是否都曾出现过。
  • 唯一环上最后处理的边，会触发第一次同根检测，两种顺序要求并不矛盾。
  • 环外的边不属于可删除答案，即使它出现在输入最后也不能返回它。
  • 合并前判断连通性，合并和路径压缩都要围绕代表根进行。

易错点总结

[!yellow]

  • 端点都出现过就判为冗余，它们可能仍属于两个不同分量。
  • 先合并再比较根，会让每一条正常边也表现为两端同根。
  • 返回最先出现的环内边，不符合输入顺序最靠后的要求；应等环被最后一条边闭合。
  • 把代表根当成固定的最小编号，没有必要，代表只需保持集合归属正确。
  • 将本结论直接套到一般有向图，会忽略有向边的方向和入度条件。

相似题目

题目 难度 关联与区别
261. 以图判树 中等 同样判断无向图中的环和树结构，本题按边顺序找到使既有连通分量形成环的那条边。
685. 冗余连接 II 困难 加入有向关系后还要处理入度为2，不能只用无向并查集找环。
547. 省份数量 中等 用并查集合并连通分量；本题找到使两端已经连通的多余边，该题按邻接矩阵合并城市。
1319. 连通网络的操作次数 中等 用并查集合并连通分量；本题找到使两端已经连通的多余边，该题统计网络连通分量与可用冗余边。
721. 账户合并 中等 用并查集合并连通分量；本题找到使两端已经连通的多余边，该题按共享邮箱合并账户。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/57837413
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！