并查集
并查集是什么
并查集是一種用來管理元素分組情況的數(shù)據(jù)結(jié)構(gòu),并查集可以高效地進(jìn)行如下操作：
查詢元素a和元素b是否屬于同一組
-
合并元素a和元素b所在組
并查集可以做什么
并查集的結(jié)構(gòu)
并查集也是使用樹形結(jié)構(gòu)實現(xiàn)的
并查集的結(jié)構(gòu)
并查集支持的操作
-
合并從一個組的根向另一個組的根連邊缺亮，這樣兩棵樹變成了一棵樹萌踱，也就把兩個組合并為一個組了。
并查集——合并 -
查詢
如果兩個節(jié)點的根相同鸳粉，就可以知道它們屬于同一組届谈。
并查集——查詢
并查集實現(xiàn)中的注意點
在樹形數(shù)據(jù)結(jié)構(gòu)中，如果發(fā)生了退化的情況咏闪，復(fù)雜度就會變得很高曙搬。在并查集中，可以按照如下方法避免退化：
-
對于每棵樹鸽嫂，記錄這棵樹的高度纵装，合并時如果兩棵樹的高度不同，從高度小的向高度大的連邊
考慮了高度的合并 -
路徑壓縮
在查詢過程中向上經(jīng)過的所有的節(jié)點据某，都改為直接連到根上
路徑壓縮
代碼實現(xiàn)
//initial the sets
void init(){
for(int i = 0; i < N; i++){
p[i] = i;
}
}
//Find(x) return the root of x
int Find(int x){
if(x == p[x]) return x;
else return p[x] = Find(p[x]);
}
//Union(x, y) union the sets of x and y
void Union(int x, int y){
int xRoot = Find(x);
int yRoot = Find(y);
if(xRoot == yRoot) return;
if(r[xRoot] < r[yRoot]) p[xRoot] = yRoot;
else if(r[xRoot] > r[yRoot]) p[yRoot] = xRoot;
else{
p[yRoot] = xRoot;
r[xRoot]++;
}
}
bool sameRoot(int x, int y){
//printf("root of %d: %d\n", x, Find(x));
//printf("root of %d: %d\n", y, Find(y));
return Find(x) == Find(y);
}
例題
- poj1182 食物鏈（中等）
- hdoj1213（簡單）
- hdoj1272（簡單）
