LeetCode并查集(UnionFind)小结

一,概述

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets UnionFind）的合并及查询问题。常常在使用中以森林来表示。 进行快速规整。

二,并查集的主要操作

"人以类聚,物以群分"
(相似的在一起(合并)
查找自己属于哪一类(查找)
两个两个是否是同一类)

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

示例如下:

 private int count;
    private int[] parents;
    
    //初始化并查集
    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++;
                }
                parents[i*n+j] = i*n+j;
            }
        }
    }
    
    public int find(int idx){
        while(idx != parents[idx]){
            //在查找的过程中压缩路径,减少查找的次数
            parents[idx] = parents[parents[idx]];
            idx = parents[idx];
        }
        return idx;
    }
 
    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        //两个元素的根不同,则合并
        if(pRoot != qRoot){
            parents[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相关题目

128. Longest Consecutive Sequence
130. Surrounded Regions
200. Number of Islands

四,推荐阅读资料

生动形象,绝逼推荐
并查集详细说明