Medium

题目描述

在本问题中，树指的是一个连通且无环的无向图。

给你一个图，该图由一个有着 n 个节点（节点值不重复1, 2, …, n）的树及一条附加的边构成。附加的边连接了两个不同的顶点，且该边不属于树中已存在的边。

图的信息记录在长度为 n 的二维数组 edges 中，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 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]

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • 没有重复的边
  • 给定的图是连通的

解题思路

这道题本质上是要找到图中形成环的最后一条边。有两种主要解法：

方法一：并查集（推荐） 并查集是解决动态连通性问题的经典数据结构。我们按照边的输入顺序，逐一加入边：

  • 对于每条边 [u, v]，先检查 u 和 v 是否已经连通
  • 如果已经连通，说明这条边会形成环，即为冗余边
  • 如果不连通，则将它们合并到同一个连通分量中

方法二：DFS 检环 对于每条边，先将其加入图中，然后用 DFS 检测是否存在环。如果存在环，则当前边就是冗余边。但这种方法时间复杂度较高。

并查集方法的优势在于时间复杂度为 O(n·α(n))，其中 α 是阿克曼函数的反函数，几乎为常数。空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool union_sets(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }
    
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        for (auto& edge : edges) {
            if (!union_sets(edge[0], edge[1])) {
                return edge;
            }
        }
        return {};
    }
};

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        parent = list(range(len(edges) + 1))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            parent[px] = py
            return True
        
        for edge in edges:
            if not union(edge[0], edge[1]):
                return edge
        
        return []

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private bool Union(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }
    
    public int[] FindRedundantConnection(int[][] edges) {
        int n = edges.Length;
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        foreach (var edge in edges) {
            if (!Union(edge[0], edge[1])) {
                return edge;
            }
        }
        
        return new int[0];
    }
}

var findRedundantConnection = function(edges) {
    const parent = {};
    
    function find(x) {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX === rootY) {
            return false;
        }
        parent[rootX] = rootY;
        return true;
    }
    
    for (const [a, b] of edges) {
        if (!union(a, b)) {
            return [a, b];
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度并查集解法
时间复杂度O(n·α(n))
空间复杂度O(n)

注：α(n) 是阿克曼函数的反函数，增长极其缓慢，实际应用中可视为常数。

相关题目