题目链接

LeetCode

题目描述

树可以看成是一个连通且 无环的 无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 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
• edges 中无重复元素
• 给定的图是连通的

  解题思路

  方法一：并查集

  在一棵树中，边的数量比节点的数量少 1。如果一棵树有 n 个节点，则这棵树有 n−1 条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 n。

树是一个连通且无环的无向图，在树中多了一条附加的边之后就会出现环，因此附加的边即为导致环出现的边。

可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。

如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。

如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为附加的边，将当前的边作为答案返回。

class Solution {
    int[] parent;
    public int[] findRedundantConnection(int[][] edges) {
        parent = new int[edges.length + 1];
        for(int i = 1; i <= edges.length; ++i){
            parent[i] = i;
        }
        for(int i = 0; i < edges.length; ++i){
            // edges[i][0] 和 edges[i][1] 已经相连
            // 如果两个有同一个祖先，则说明edges[i][0] 和 edges[i][1]可以去掉
            // 否则将两个连线连接
            if(find(edges[i][0]) != find(edges[i][1])){
                union(edges[i][0], edges[i][1]);
            }else{
                return edges[i];
            }
        }
        return new int[0];
    }
    private int find(int i){
        // 未压缩
        // if(parent[i] == i){
        //     return i;
        // }else{
        //     return find(parent[i]);
        // }
        // 路径压缩
        if(parent[i] != i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }
    private void union(int i, int j){
        parent[find(i)] = find(j);
    }
}

• 时间复杂度 O(n log n)
• 空间复杂度 O(n)