一,概述

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets UnionFind）的合并及查詢問(wèn)題。常常在使用中以森林來(lái)表示。 進(jìn)行快速規(guī)整。

二,并查集的主要操作

"人以類(lèi)聚,物以群分"
(相似的在一起(合并)
查找自己屬于哪一類(lèi)(查找)
兩個(gè)兩個(gè)是否是同一類(lèi))

• 1,初始化一個(gè)并查集 initUnionFind
  初始化并查集,一般是將每個(gè)元素作為一個(gè)單獨(dú)的集合,對(duì)于下面的示例就是對(duì)應(yīng)的元素父節(jié)點(diǎn)就是自己
• 2,合并兩個(gè)不相交集合 union
  兩個(gè)元素,分別找到(find)他們的根節(jié)點(diǎn),然后將其中一個(gè)元素的根節(jié)點(diǎn)的父親指向另外的一個(gè)元素的根節(jié)點(diǎn)
• 3,查找某個(gè)元素的根節(jié)點(diǎn) find
  查找一個(gè)元素的根節(jié)點(diǎn),parent--->parent--->parent.....
  那么問(wèn)題來(lái)了,查找元素根節(jié)點(diǎn)途徑的元素過(guò)多,那么就有一個(gè)優(yōu)化的問(wèn)題-------路徑壓縮,直接將該元素的父親指向根節(jié)點(diǎn)或者祖先
• 4,判斷兩個(gè)元素是否屬于同一個(gè)集合 isConnected
  判斷兩個(gè)元素是否屬于同一個(gè)集合,就是分別找到他們的根節(jié)點(diǎn),然后判斷兩個(gè)根節(jié)點(diǎn)是否相等.

示例如下:

 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]){
            //在查找的過(guò)程中壓縮路徑,減少查找的次數(shù)
            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);
        //兩個(gè)元素的根不同,則合并
        if(pRoot != qRoot){
            parents[qRoot] = pRoot;
            count--;
        }
    }
    
    public boolean isConnected(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        
        //兩點(diǎn)不連通
        if(pRoot != qRoot){
            return false;
        }
        return false;
    }

三,LeetCode相關(guān)題目

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

四,推薦閱讀資料

生動(dòng)形象,絕逼推薦
并查集詳細(xì)說(shuō)明