冗余连接

684. 冗余连接 - 力扣（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 中无重复元素
• 给定的图是连通的

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

class Solution {
     class UnionFind{
        int[] father;
        public UnionFind(int n) {
            father = new int[n+1];
            for(int i = 1; i <= n; i++){
                father[i] = i;
            } 
        }

        public int find(int u) {
            if(father[u] == u) return u;
            father[u] = find(father[u]); //路径优化，让u的父节点指向根
            return father[u];
        }

        public boolean isSame(int u, int v) {
            return find(u) == find(v);
        }

        public void join(int u, int v) {
            u = find(u); //找u的父亲
            v = find(v); //找v的父亲
            if(u != v) {
                father[v] = u;
            }
        }
    }


    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length);

        for(int i = 0; i < edges.length; i++){
            //图已经连通了，直接返回结果
            if(uf.isSame(edges[i][0], edges[i][1])){
                return new int[] {edges[i][0],edges[i][1]};
            }
            //如果图未连通，依次连接遍历的点
            uf.join(edges[i][0], edges[i][1]);
        }
        return new int[]{};

    }
}