# 一、综述 不相交集合数据结构（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的脱机最小公共祖先算法