剑指offer118：多余的边

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

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

分析：

为了找到多余的边需要解决两个问题：一是如何判断两个节点是否属于同一个子图，而是如何合并两个子图。并查集刚好可以解决这两个问题。

函数union和116题类似不再赘述。

由于题目指出节点的编号从1到n，逐一扫描边的数组edges得到最大的节点编号确定n的值。接下来初始化并查集，将n个节点初始化为n个子集，每个节点的根节点都指向它自己，即fathers[i] = i，接下来逐一在图中添加边，直到某条边的两个节点属于同一个子集，此时函数union将返回false。添加这条边将导致图中出现环，对树而言这条边就是多余的。

假设图中有n个节点，n条边。在采用路径压缩之后，在并查集上的合并，查找操作的时间复杂度可以近似看成O（1），因此这种解法的时间复杂度是O（n)。

代码：

package com.kuang;

public class FindRedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        int maxVertex = 0;
        for (int[] edge:edges){
            maxVertex = Math.max(maxVertex,edge[0]);
            maxVertex = Math.max(maxVertex,edge[1]);
        }
        int[] fathers = new int[maxVertex+1];
        for (int i = 0; i <= maxVertex; i++) {
            fathers[i] = i;
        }
        for (int[] edge : edges) {
            if (!union(fathers,edge[0],edge[1])){
                return edge;
            }
        }
        return new int[2];
    }

    private boolean union(int[] fathers, int i, int j) {
        int fatherI = findFather(fathers,i);
        int fatherJ = findFather(fathers,j);
        if (fatherI != fatherJ){
            fathers[fatherI] = fatherJ;
            return true;
        }
        return false;
    }

    private int findFather(int[] fathers, int i) {
        if (fathers[i] != i){
            fathers[i] = findFather(fathers,fathers[i]);
        }
        return fathers[i];
    }
}