http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html并查集：(union-find sets)是一種簡單的用途廣泛的集合. 并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，應用很多，如其求無向圖的連通分量個數、最小公共祖先、帶限制的作業排序，還有最完美的應用：實現Kruskar算法求最小生成樹。其實，這一部分《算法導論》講的很精煉。
一般采取樹形結構來存儲并查集，在合并操作時可以利用樹的節點數(加權規則)或者利用一個rank數組來存儲集合的深度下界--啟發式函數，在查找操作時進行路徑壓縮使后續的查找操作加速。這樣優化實現的并查集，空間復雜度為O(N)，建立一個集合的時間復雜度為O(1)，N次合并M查找的時間復雜度為O(M Alpha(N))，這里Alpha是Ackerman函數的某個反函數，在很大的范圍內這個函數的值可以看成是不大于4的，所以并查集的操作可以看作是線性的。
它支持以下三種操作:
－Union (Root1, Root2) //合并操作；把子集合Root2和子集合Root1合并.要求：Root1和 Root2互不相交,否則不執行操作.
－Find (x) //搜索操作；搜索元素x所在的集合,并返回該集合的名字--根節點.
－UFSets (s) //構造函數。將并查集中s個元素初始化為s個只有一個單元素的子集合.
－對于并查集來說，每個集合用一棵樹表示。
－集合中每個元素的元素名分別存放在樹的結點中，此外，樹的每一個結點還有一個指向其雙親結點的指針。
－為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標識集合。
以下給出我的兩種實現:
1
//Abstract: UFSet
2
3//Author:Lifeng Wang （Fandywang）
4
5
6
7
8// Model One 與Model 2 路徑壓縮方式不同,合并標準不同
9
10const int MAXSIZE = 500010;
11
12int rank[MAXSIZE]; // 節點高度的上界
13
14int parent[MAXSIZE]; // 根節點
15
16
int FindSet(int x)
{// 查找+遞歸的路徑壓縮
17
18 if( x != parent[x] ) parent[x] = FindSet(parent[x]);
19
20 return parent[x];
21
22
}
23
24void Union(int root1, int root2){
25
26 int x = FindSet(root1), y = FindSet(root2);
27
28 if( x == y ) return ;
29
30 if( rank[x] > rank[y] ) parent[y] = x;
31
32
else{
33
34 parent[x] = y;
35
36 if( rank[x] == rank[y] ) ++rank[y];
37
38
}
39
40}
41
42void Initi(void){
43
44 memset(rank, 0, sizeof(rank));
45
46 for( int i=0; i < MAXSIZE; ++i ) parent[i] = i;
47
48}
49
50
51
52
53// Model Two
54
55const int MAXSIZE = 30001;
56
57int pre[MAXSIZE]; //根節點i,pre[i] = -num,其中num是該樹的節點數目;
58
59 //非根節點j,pre[j] = k,其中k是j的父節點
60
61int Find(int x){//查找+非遞歸的路徑壓縮
62
63 int p = x;
64
65 while( pre[p] > 0 ) p = pre[p];
66
67 while( x != p ){
68
69 int temp = pre[x]; pre[x] = p; x = temp;
70
71 }
72
73 return x;
74
75}
76
77void Union(int r1, int r2){
78
79 int a = Find(r1); int b = Find(r2);
80
81 if( a == b ) return ;
82
83 //加權規則合并
84
85 if( pre[a] < pre[b] ){
86
87 pre[a] += pre[b]; pre[b] = a;
88
89 }
90
91 else {
92
93 pre[b] += pre[a]; pre[a] = b;
94
95 }
96
97}
98
99void Initi(void)
100
101{
102
103 for( int i=0; i < N; ++i ) pre[i] = -1;
104
105}
106
107
并查集的一些題目和我的相關解題報告:
POJ 1611 The Suspects 最基礎的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物鏈 并查集的拓展
注意: 只有一組數據;
要充分利用題意所給條件:有三類動物A,B,C，這三類動物的食物鏈
構成了有趣的環形。A吃B， B吃C，C吃A。也就是說:只有三個group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度優先遍歷
每次遍歷記錄下該點是男還是女，只有:男-〉女，女-〉男滿足，否則，找到同性戀，結束程序。
法二:二分圖匹配
法三:并查集的拓展:和1182很像，只不過這里就有兩組，而1182是三組,1611無限制
POJ 1861 Network == zju_1542 并查集+自定義排序+貪心求"最小生成樹"
答案不唯一，不過在ZOJ上用QSORT()和SORT()都能過，在POJ上只有SORT()才能過...
POJ 1703 Find them, Catch them 并查集的拓展
這個和POJ 2492 A Bug's Life很像，就是把代碼稍微修改了一下就AC了！
注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是說只有兩個組。
POJ 2236 Wireless Network 并查集的應用
需要注意的地方：1、并查集；2、N的范圍，可以等于1001；3、從N+1行開始，第一個輸入的可以是字符串。
POJ 1988 Cube Stacking 并查集很好的應用
1、與 銀河英雄傳說==NOI2002 Galaxy一樣；2、增加了一個數組behind[x],記錄戰艦x在列中的相對位置；3、詳細解題報告見銀河英雄傳說。
JOJ 1905 Freckles == POJ 2560 最小生成樹
法一：Prim算法；法二：并查集實現Kruskar算法求最小生成樹
JOJ 1966 Super Market III == PKU 1456 Supermarket 帶限制的作業排序問題（貪心+并查集）
提高題目：
POJ 2912 Rochambeau
POJ 1733 Parity game
POJ 1308 Is It A Tree?
posted on 2009-04-21 14:56
wyiu 閱讀(183)
評論(0) 編輯 收藏 引用 所屬分類:
算法