题目
树可以看成无环的无向图。在一个包含n个节点（节点标号为从1到n）的树中添加一条边连接任意两个节点，这棵树就会变成一个有环的图。给定一个在树中添加了一条边的图，请找出这条多余的边（用这条边连接的两个节点表示）。输入的图用一个二维数组edges表示，数组中的每个元素是一条边的两个节点[u，v]（u＜v）。如果有多个答案，请输出在数组edges中最后出现的边。
例如，如果输入数组edges为[[1，2]，[1，3]，[2，4]，[3，4]，[2，5]]，则它对应的无向图如图15.25所示。输出为边[3，4]。
分析
先在图中添加一条边[1，2]，于是将节点1和节点2所在的子图连在一起，形成一个有两个节点的子图，如图（a）所示。接下来添加一条边[1，3]。由于节点1和节点3分别属于两个不同的子图，添加这条边就将两个子图连成一个包含3个节点的子图，如图（b）所示。再在图中添加一条边[2，4]。由于节点2和节点4分别属于两个不同的子图，添加这条边就将两个子图连成一个包含4个节点子图，如图（c）所示。然后在图中添加一条边[3，4]。此时节点3和节点4属于同一个子图，添加边[3，4]导致图中出现了一个环，如图（d）所示。最后添加边[2，5]。节点2和节点5属于不同的子图，这条边将两个子图连在一起形成一个包含5个节点的子图。
解
public class Test {
public static void main(String[] args) {
int[][] edges = {
{
1, 2}, {
1, 3}, {
2, 4}, {
3, 4}, {
2, 5}};
int[] result = findRedundantConnection(edges);
System.out.println(result[0] + " " + result[1]);
}
public static 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 = 1; i <= maxVertex; i++) {
fathers[i] = i;
}
for (int[] edge : edges) {
if (!union(fathers, edge[0], edge[1])) {
return edge;
}
}
return new int[2];
}
private static boolean union(int[] fathers, int i, int j) {
int fatherOfI = findFather(fathers, i);
int fatherOfJ = findFather(fathers, j);
if (fatherOfI != fatherOfJ) {
fathers[fatherOfI] = fatherOfJ;
return true;
}
return false;
}
private static int findFather(int[] fathers, int i) {
if (fathers[i] != i) {
fathers[i] = findFather(fathers, fathers[i]);
}
return fathers[i];
}
}
