4.并查集Disjoint Set

集合。在集合中将各个元素划分为若干个 互不相交的子集。

• 如何表示"集合"关系?

用互不相交的树，表示多个“集合”。这些树构成一个森林。

---

并查集（Disjoint Set）是逻辑结构集合的一种具体实现，只进行“并”和“查”两种基本操作。

4.1查

• 如何“查”到一个元素到底属于哪一个集合?

从指定元素出发，一路向上，找到根节点。

• 如何判断两个元素是否属于同一个集合?

分别查到两个元素的根，判断根节点是否相同即可。

4.2并

• 如何把两个集合合并一个集合?

让一棵树成为另一棵树的子树即可。

❗4.3代码实现

因为只需要查找到根结点来判断是不是一个根节点（一个集合），所以使用双亲表示法来实现树的存储，表示一个集合。

Find ：“查”操作:确定一个指定元索所属集合。

最坏时间复杂度O(n)：n个结点全是上一个的孩子

所有我们的优化就是尽量不让树长高。

Union：“并”操作:将两个不想交的集合合并为一个。

时间复杂度O(1)

#include<stdio.h>
#include<stdlib.h>
#define SIZE 10
int UFsets[SIZE];	//集合元素数组//初始化并查集，S相当于父结点，一开始都是一个节点，所以都是-1
void Initial(int S[]){for (int i=0; i<SIZE; i++)S[i]=-1;
}//Find“查”操作，找x所属集合(返回x所属根结点)
int Find(int S[], int x){while(S[x] >= 0)	//循环寻找x的根x=S[x];		//寻找它的父结点return x;	//根的S[]小于0(就是等于-1表示树的根)
}//Union“并”操作，将两个集合合并为一个(把一个树的根变成另一个树的根的孩子)
void Union(int S[], int x, int y){int rootx=Find(S,x);int rooty=Find(S,y);//要求x与y是不同的集合if(rootx!=rooty){S[rooty] = rootx;//将根Root2连接到另一根Root1下面}
}//判断元素x和y是否属于同一集合
int IsSame(int S[],int x,int y){if (Find(S,x)==Find(S,y))return 1;elsereturn 0;
}int main(){int S[SIZE];Initial(S);printf("初始状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");Union(S,0,1);Union(S,1,2);Union(S,2,3);Union(S,3,4);Union(S,4,5);printf("1-5合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");Union(S,0,7);printf("7  合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");printf("%d\n",Find(S,5));printf("%d\n",Find(S,6));return 0;
}

初始状态：-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1-5合并后的状态：-1 0 0 0 0 0 -1 -1 -1 -1

7 合并后的状态：-1 0 0 0 0 0 -1 0 -1 -1

0
6

另一种写法：

假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

//或者写成：用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。
int find(int x){if(fa[x] == x)return x;elsereturn find(fa[x]);
}//合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。
void merge(int i, int j){fa[find(i)] = find(j);
}

这里的Find可以简写为一行：

int find(int x){return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

注意赋值运算符=的优先级没有三元运算符?:高，这里要加括号。

4.4对union优化

我们的优化目标是尽量不让树的高度更高，提高查找效率。

//Union“并”操作，将两个集合合并为一个(把一个树的根变成另一个树的根的孩子)
void Union(int S[], int x, int y){int rootx=Find(S,x);int rooty=Find(S,y);//要求x与y是不同的集合if(rootx == rooty){return;}if(S[rootx] <= S[rooty]){ 	//x结点数更多(因为是负数)S[rootx] += S[rooty];	//累加结点总数S[rooty] = rootx; 		//小树y合并到大树x}else {S[rooty] += S[rootx];	//累加结点总数S[rootx] = rooty; 		//小树x合并到大树y}
}

该方法构造的树高不超过$\lfloor lo{g}_{2}n\rfloor +1$。

使得 Find 的最坏时间复杂度变为$O(lo{g}_{2}n)$

4.5对Find的优化（压缩路径）

压缩路径：Find 操作，先找到根节点，再将查找路径上所有结点都挂到根结点下。

每次Find操作，先找根，再“压缩路径”，可使树的高度不超过O(α(n))。

α(n)是一个增长很缓慢的函数，对于常见的n值，迪常α(n)≤4，因此优化后并查集的Find、Union操作时间开销都很低。

//Find“查”操作优化，先找到根节点，再进行“压缩路径”
// 将查找路径上所有结点都挂到根结点下
int Find(int S[], int x){int root = x;while(S[root] >= 0)root=S[root];   //循环找到根
//压缩路径while(x != root){	//将查找路径上所有结点都挂到根结点下int temp=S[x];	//temp指向x的父节点S[x]=root;	    //把x直接挂到根节点下x=temp;         //继续操作x的父结点，准备也挂在root节点下}return root;//返回根节点编号
}

❗4.6并查集C代码（优化后）

#include<stdio.h>
#include<stdlib.h>
#define SIZE 10
int UFsets[SIZE];	//集合元素数组//初始化并查集，S相当于父结点，一开始都是一个节点，所以都是-1
void Initial(int S[]){for (int i=0; i<SIZE; i++)S[i]=-1;
}//Find“查”操作优化，先找到根节点，再进行“压缩路径”
// 将查找路径上所有结点都挂到根结点下
int Find(int S[], int x){int root = x;while(S[root] >= 0)root=S[root];   //循环找到根
//压缩路径while(x != root){	//将查找路径上所有结点都挂到根结点下int temp=S[x];	//temp指向x的父节点S[x]=root;	    //把x直接挂到根节点下x=temp;         //继续操作x的父结点，准备也挂在root节点下}return root;//返回根节点编号
}//Union“并”操作，将两个集合合并为一个(把一个树的根变成另一个树的根的孩子)
void Union(int S[], int x, int y){int rootx=Find(S,x);int rooty=Find(S,y);//要求x与y是不同的集合if(rootx == rooty){return;}if(S[rootx] <= S[rooty]){ 	//x结点数更多(因为是负数)S[rootx] += S[rooty];	//累加结点总数S[rooty] = rootx; 		//小树y合并到大树x}else {S[rooty] += S[rootx];	//累加结点总数S[rootx] = rooty; 		//小树x合并到大树y}
}//判断元素x和y是否属于同一集合
int IsSame(int S[],int x,int y){if (Find(S,x)==Find(S,y))return 1;elsereturn 0;
}int main(){int S[SIZE];Initial(S);printf("初始状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");Union(S,0,1);printf("1  合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");Union(S,1,2);Union(S,2,3);Union(S,3,4);Union(S,4,5);printf("2-5合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n");Union(S,0,7);printf("7  合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d ",S[i]);printf("\n\n");return 0;
}

初始状态：-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 合并后的状态：-2 0 -1 -1 -1 -1 -1 -1 -1 -1
2-5合并后的状态：-6 0 0 0 0 0 -1 -1 -1 -1
7 合并后的状态：-7 0 0 0 0 0 -1 0 -1 -1

按秩合并

#include<stdio.h>
#include<stdlib.h>#define SIZE 10
const int maxn = 5005;
int Fa[maxn],Rank[maxn];//初始化（按秩合并）
void init(int n){for (int i=0; i<n; i++){Fa[i] = i;Rank[i] = 1;}
}int find(int x){return x == Fa[x]? x:(Fa[x] = find(Fa[x]));//路径压缩
}//合并（按秩合并）void merge(int i, int j) {int x = find(i), y = find(j);if (Rank[x] < Rank[y]){     //小树合并到大树Fa[x] = y;}else{Fa[y] = x;}// 合并完更新rank秩if (Rank[x] == Rank[y] && x!=y){Rank[y]++;}
}int main(){init(SIZE);printf("初始状态：");for(int i=0;i<SIZE;i++) printf("%d(%d) ",Fa[i],Rank[i]);printf("\n");merge(0,1);printf("1  合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d(%d) ",Fa[i],Rank[i]);printf("\n");merge(1,2);merge(2,3);merge(3,4);merge(4,5);printf("2-5合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d(%d) ",Fa[i],Rank[i]);printf("\n");merge(2,7);printf("7  合并后的状态：");for(int i=0;i<SIZE;i++) printf("%d(%d) ",Fa[i],Rank[i]);printf("\n\n");return 0;
}

初始状态：0(1) 1(1) 2(1) 3(1) 4(1) 5(1) 6(1) 7(1) 8(1) 9(1)
1 合并后的状态：0(1) 0(2) 2(1) 3(1) 4(1) 5(1) 6(1) 7(1) 8(1) 9(1)
2-5合并后的状态：0(1) 0(2) 0(2) 0(2) 0(2) 0(2) 6(1) 7(1) 8(1) 9(1)
7 合并后的状态：0(1) 0(2) 0(2) 0(2) 0(2) 0(2) 6(1) 0(2) 8(1) 9(1)