# 一、綜述 不相交集合數據結構（disjoint-set data struct）保持一組不相交的動態集合S={S1,S2,……,Sk} 這種數組結構支持三種操作： （1）MAKE-SET(x)：構造一種只有元素x的集合 （2）UNION(x,y)：合并兩個集合 （3）FIND-SET(x)：找出元素x所屬的集合 # 二、代碼 ### 1.UnionFindSet.h ~~~ /* UnionFindSet.h 并查集，非遞歸方法，含路徑壓縮，數組從0開始 */ #include <iostream> using namespace std; #define MAXN 30005 class UFS { public: int n; int p[MAXN+1];//集合根結點 int rank[MAXN+1]; //集合中點的個數 public: UFS(int size = MAXN); void clear(); int Find_Set(int x); //a并入b中，不區分大小 void Union(int x, int y); void Make_Set(int x); void Link(int x, int y); }; UFS::UFS(int size):n(size) { //必須從0開始 for(int i = 0; i <= n; i++) Make_Set(i); } void UFS::Make_Set(int x) { p[x] = x; rank[x] = 0; } void UFS::clear() { for(int i = 0; i <= n; i++) Make_Set(i); } int UFS::Find_Set(int x) { if(x != p[x]) p[x] = Find_Set(p[x]); return p[x]; } void UFS::Union(int x, int y) { Link(Find_Set(x), Find_Set(y)); } void UFS::Link(int x, int y) { if(rank[x] > rank[y]) p[y] = x; else { p[x] = y; if(rank[x] == rank[y]) rank[y]++; } } ~~~ # 三、練習 ### 21.1 不相交集合上的操作 21.1-1 ~~~ Input:d i Output:a b c e f g h i j k Input:f k Output:a b c e g h i j k Input:g i Output:a b c e h i j k Input:b g Output:a c e h i j k Input:a h Output:c e h i j k Input:i j Output:c e h i k Input:d k Output:c e h i Input:b j Output:c e h i Input:d f Output:c e h i Input:g j Output:c e h i Input:a e Output:c h i Press any key to continue ~~~ 21.1-3 FIND-SET 2|E|次 UNION |E|次 ### 21.2 不相交集合的鏈表表示 21.2-1 ~~~ void Make_Set(int x) { S[x].head = x; S[x].tail = x; S[x].size = 1; n[x].rep = x; n[x].next = 0; } int Find_Set(int x) { return n[x].rep; } void Union(int x, int y) { x = n[x].rep; y = n[y].rep; if(S[x].size >S[y].size) swap(x, y); n[S[y].tail].next = S[x].head; S[y].size = S[y].size + S[x].size; int i; for(i = S[x].head; i != 0; i = n[i].next) n[i].rep = y; S[x].head = 0; } ~~~ 21.2-2 16 16 21.2-5 ~~~ void Union2(int x, int y) { x = n[x].rep; y = n[y].rep; if(x == y) return ; if(S[x].size >S[y].size) swap(x, y); S[y].size = S[y].size + S[x].size; int i; for(i = S[x].head;; i = n[i].next) { n[i].rep = y; if(n[i].next == 0) { n[i].next = n[S[y].head].next; break; } } n[S[y].head].next = S[x].head; S[x].head = 0; } ~~~ ### 21.3 不相交集合森林 21.3-2 ~~~ void UFS::Find_Set2(int x) { int ret = x, t; while(ret != p[ret]) ret = p[ret]; while(p[x] != ret) { t = p[x]; p[x] = ret; x = p[x]; } } ~~~ 21.3-3 題目的意思不懂 # 四、思考題 ### 21-1脫機最小值 ### 21-2深度確定 見[算法導論 第21章 21-2 深度確定](http://blog.csdn.net/mishifangxiangdefeng/article/details/8231652) ### 21-3Tarjan的脫機最小公共祖先算法