并查集(union-find set)
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。
并查集的主要操作
1. 初始化集合(Make_Set(x))
把每一个元素初始化为一个集合,初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身(也可以根据情况而变)。
2. 合并不相交的两个集合(Union(x,y))
合并操作很简单:先设置一个数组Father[x],表示x的“父亲”的编号。那么,合并两个不相交集合的方法就是,找到其中一个集合最父亲的父亲(也就是最久远的祖先),将另外一个集合的最久远的祖先的父亲指向它。
3. 判断两个元素是否是同一个集合(Find_Set(x))
本操作可转换为寻找两个元素的最久远祖先是否相同。可以采用递归实现。
并查集优化
1. Find_Set(x)时,路径压缩
寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示;可见,路径压缩方便了以后的查找。
2. Union(x,y)时,按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
主要代码实现
int father[MAX]; /* father[x]表示x的父节点*/
int rank[MAX]; /* rank[x]表示x的秩*/
/* 初始化集合*/
void Make_Set(int x)
{
father[x] = x; //根据实际情况指定的父节点可变化
rank[x] = 0; //根据实际情况初始化秩也有所变化
}
/* 查找x元素所在的集合,回溯时压缩路径*/
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华
}
return father[x];
}
/*
按秩合并x,y所在的集合
下面的那个if else结构不是绝对的,具体根据情况变化
但是,宗旨是不变的即,按秩合并,实时更新秩。
*/
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
复杂度分析
空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内(人类目前观测到的宇宙范围估算有10的80次方个原子,这小于前面所说的范围)这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的。
应用
并查集常作为另一种复杂的数据结构或者算法的存储结构。常见的应用有:求无向图的连通分量个数,最近公共祖先(LCA),带限制的作业排序,实现Kruskar算法求最小生成树等。
经典题目练习
POJ1611
思路:
典型的并查集,最初各自为集,然后每个group进行合并,等到所有的group合并完,题目也就解决了,因为在合并的时候,如果哪两个group中有重合的元素,则那个后来的group会由于按秩合并的原则自动合并到先有的集合当中。
代码:
#include <stdio.h>
#include <stdlib.h>
#define N 30005
int n,m,i,j;
int father[N],num[N];
//初始化各自的father为本身
void MakeSet(int n){
for(i=0;i<n;i++){
father[i] = i;
num[i]=1;
}
}
//递归的findset
int FindSet(int x){
if(x != father[x]){
father[x] = FindSet(father[x]);
}
return father[x];
}
void UnionSet(int a,int b){
int x = FindSet(a);
int y = FindSet(b);
if(x == y){
return;
}
if(num[x] > num[y]){
father[y] = x;
num[x] += num[y];
}else{
father[x] = y;
num[y] += num[x];
}
}
int main(void) {
while(scanf("%d %d",&n,&m) != EOF && n != 0){
MakeSet(n);
for(i=0;i<m;i++){
int count,first,x;
scanf("%d %d",&count,&first);
for(j=1;j<count;j++){
scanf("%d",&x);
UnionSet(first,x);
}
}
printf("%d\n",num[FindSet(0)]);
}
return EXIT_SUCCESS;
}
-1做根和使用非递归实现的代码
void MakeSet(int n){
for(i=0;i<n;i++){
father[i] = -1;
num[i]=1;
}
}
int FindSet(int x){
while(father[x] != -1){
x = father[x];
}
return x;
}
- 大小: 11.9 KB
- 大小: 8.8 KB
分享到:
相关推荐
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复...
数据结构 并查集 查询 快速 实用 ACM
并查集 第12章 并查集
并查集模板并查集模板并查集模板并查集模板并查集模板并查集模板
深入理解并查集算法,细致讲解,专业老师,一步到位 。
学习并查集的好东东,需要的看看吧,ACM之路
并查集讲义,清楚明白地讲解并查集原理及优化
并查集详解
并查集,acm,并查集的入门课件,主要使用与ACM学习
C++版并查集的课件,定义,并查集的精髓代码以及路径压缩的内容
C++整理\并查集\并查集初步.ppt 并查集初步
在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一...即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集的简介,用法,以及一些例子
算法与数据结构:并查集实现的方法,以及ACM并查集的一些例子
并查集原理和代码实现。或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们...
关于并查集的几道经典题目,希望对大家有所帮助
并查集的一些基础知识讲解,详细的PPT,希望对搜索者有帮助!
最经典并查集详细讲解, 最经典并查集详细讲解。
使用C++实现了并查集的建立,合并和查找功能,并附简单的测试用例。