一个树即无向图，添加一条边成为无向有环图，去除多余的边，使得图成为无环图。同理可以推广到去除多个边。
/**
* 有环图去除一条边使得无环图。
* 遍历到一条边时，如果两个点不连通，则属于不同的连通分量，对两个进行合并即可
* 否则添加该条边则成环。
* @param edges
* @return
*/
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int parent[] = new int[n + 1];
//边进行初始化，初始化自己为父结点
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < n; i++) {
int edge[] = edges[i];
int node1 = edge[0];
int node2 = edge[1];
//不连通，则进行连通合并，从起点指向父结点
if (find(parent, node1) != find(parent, node2)) {
union(parent, node1, node2);
} else {
return edge;
}
}
return new int[0];
}
public void union(int parent[], int index1, int index2) {
//起点父结点调整为终点结点
parent[find(parent, index1)] = find(parent, index2);
}
public int find(int parent[], int index) {
//递归寻找父结点
if (parent[index] != index) {
parent[index] = find(parent, parent[index]);
}
return parent[index];
}
