一,概述
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets UnionFind）的合并及查詢問題诱告。常常在使用中以森林來表示晨雳。 進(jìn)行快速規(guī)整。
二,并查集的主要操作
"人以類聚,物以群分"
(相似的在一起(合并)
查找自己屬于哪一類(查找)
兩個(gè)兩個(gè)是否是同一類)
- 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.....
那么問題來了,查找元素根節(jié)點(diǎn)途徑的元素過多,那么就有一個(gè)優(yōu)化的問題-------路徑壓縮,直接將該元素的父親指向根節(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]){
//在查找的過程中壓縮路徑,減少查找的次數(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
