一、原文链接
http://blog.csdn.net/u014507083/article/details/71194740?locationNum=5&fps=1
二、算法理解
处理一个森林。当如果希望能够将某棵树并入另一棵树下时使用。
三、算法实现
1、查找根节点
public static int findParent(int target,int[] parent){
int parentIndex = target;
//不断递归去查找根节点，当panretIndex = parent[parentIndex]时即表示找到该树的根
while (parent[parentIndex] != parentIndex)
parentIndex = parent[parentIndex];
int i = target;
//路径压缩，让target节点及target节点的父节点指向根节点
while (i != parentIndex){
i = parent[i];
parent[i] = parentIndex;
}
return parentIndex;
}
2、合并树
public static void join(int target1,int target2,int[] parent){
int root1 = findParent(target1,parent);
int root2 = findParent(target2,parent);
if (root1 != root2)
parent[root1] = root2;
}
