并查集是一种树型的数据结构，通常用于检测图的联通性。 一般用一个数组来保存集合的状态，index代表点，value表示属于的集合，相当于pinter指向相连的一个点。一般分为下列步骤。

1,初始化一个并查集 initUnionFind 初始化并查集,一般是将每个元素作为一个单独的集合,对于下面的示例就是对应的元素父节点就是自己 2,合并两个不相交集合 union 两个元素,分别找到(find)他们的根节点,然后将其中一个元素的根节点的父亲指向另外的一个元素的根节点 3,查找某个元素的根节点 find 查找一个元素的根节点,father--->father--->father..... 那么问题来了,查找元素根节点途径的元素过多,那么就有一个优化的问题-------路径压缩,直接将该元素的父亲指向根节点或者祖先 4,判断两个元素是否属于同一个集合 isConnected 判断两个元素是否属于同一个集合,就是分别找到他们的根节点,然后判断两个根节点是否相等.

    private int count;
    private int[] father;

    //初始化并查集
    public void initUnionFind(int m, int n, char[][] grid){
        parents = new int[m*n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == '1'){
                    count++;
                }
                father[i*n+j] = i*n+j;
            }
        }
    }

    public int find(int idx){
        while(idx != father[idx]){
            //在查找的过程中压缩路径,减少查找的次数
            father[idx] = father[father[idx]];
            idx = father[idx];
        }
        return idx;
    }

    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        //两个元素的根不同,则合并
        if(pRoot != qRoot){
            father[qRoot] = pRoot;
            count--;
        }
    }

    public boolean isConnected(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);

        //两点不连通
        if(pRoot != qRoot){
            return false;
        }
        return false;
    }

LeetCode:题目

1. Longest Consecutive Sequence
2. Surrounded Regions
3. Number of Islands