树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

解题思路：并查集

⭕ 先分析一波

如果按照edges数组从左到右的顺序，去构造图，遇到的第一个变成环的边就是我们要去除的边！并且它满足edges中最后出现的边。（如果要删除第一个出现环的边，就从右到左构造！）
——关键是我们怎么知道图是否已经成环？
● 利用【并查集】！我们知道并查集的特点是能将连通的点划分到同一个集合中。
也就是说我们在构造的时候，如果边两端的点不在同一个集合，那么我们合并它们；
但是如果在同一个集合，说明已经连通，此时再把边添加到图中，就会成环！

class Solution {
    private int[] connect;
    public int[] findRedundantConnection(int[][] edges) {
        // 因为要找edges靠右出现的边，因此从左向右构造图，遇到第一个构成环的则返回
        // 构成环如何判断？边的两个端点如果在同一个集合中，如果再添加这条边，一定会成环！
        connect = new int[edges.length+1];
        // 初始化并查集
        for(int i=0; i<connect.length; i++){
            connect[i] = i;
        }
        int i = 0;
        for(; i<edges.length; i++){
            if(!merge(edges[i][0], edges[i][1])) break;
        }
        return new int[]{edges[i][0], edges[i][1]};
    }
    public int find(int x){
        while(x != connect[x]){
            x = connect[x];
        }
        return x;
    }
    // 如果x、y已经是同一个集合中，则说明再加就会成环，返回合并false
    public boolean merge(int x, int y){
        int x_root = find(x);
        int y_root = find(y);
        if(x_root != y_root){
            connect[x_root] = y_root;
            return true;
        }else return false;
    }
}