并查集

一、原文链接

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;
    }