昨天看了几篇有关并查集的论文,对理解并查集很有帮助,在这里写篇博客来记录下自己对并查集的简单理解,以及并查集的简单运用。
并查集的分析
并查集的概念主要是处理集合问题(或可抽象成集合概念的问题),首先数学上的集合概念做个初步的分析
首先,我们从数学的角度给出等价关系和等价类的定义:
定义1:如果集合S中的关系R是自反的,对称的,传递的,则称他为一个等价关系。
——自反:x=x;
——对称:若x=y,则y=x;
——传递:若x=y、y=z,则x=z。?要求:x、y、z必须要同一个子集中。
定义2:如果R是集合S的等价关系。对于任何x∈S,由[x]R={y|y∈S and xRy}给出的集合[x]RS
称为由x∈S生成的一个R的等价类。
定义3:若R是集合S上的一个等价关系,则由这个等价关系可产生这个集合的唯一划分。
即可以按R将S划分为若干不相交的子集S1,S2,S3,S4,…,他们的并即为S,则这
些子集Si变称为S的R等价类。
划分等价类的问题的提法是:要求对S作出符合某些等价性条件的等价类的划分,已知
集合S及一系列的形如“x等价于y”的具体条件,要求给出S的等价类的划分,符合所
列等价性的条件。(我们上面提到的联系,即可认为是一个等价关系,我们就是要将
集合S划分成n个联系的子集,然后再判断x,y是否在一个联系子集中。)
这三个基本定义对理解并查集的概念及相应的操作非常有帮助。
并查集的操作主要有三个:
1.划分等价类,这个在预处理的时候进行,很简单,就是有多少元素就划分多少等价类即pre[i]=i,很好理解,为下面的合并做好准备。
2.找根节点(溯源) 我通常用函数root(int x)来实现找x的最终祖先。
3.合并,就是将两个集合合为一个集合。
用算法实现三个方法:
1.预处理
void init(int n){ int i; for(i=1;i<=n;++i){ pre[i] = i; } }
int root(int x){ if(x!=pre[x]){ pre[x] = root(pre[x]); } return pre[x]; }溯源这里是有优化的,判断两个元素是否属于同一集合需要O(n)的时间,但这里可以使用路径压缩来进行优化, 路径压缩实际上是在找完根结点之后,在递归回来的时候顺便把路径上元素的父亲指针都指向根结点
3.合并
void merge(int a,int b){ int x = root(a); int y = root(b); if(x!=y){ pre[x]=y; } }
合并就是先找到a和b各自的源,然后把源连起来则两个集合就实现了合并。
一上这三个函数就是并查集的核心思想和方法,以后的解题关键就是能将问题抽象成集合并应用并查集来解决了。
并查集的应用
下面我们就以以上并查集的思想解决一个实际问题来简单运用一下。
以解决 HDU 1232为例。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232
题目在这里就不再赘述了,经过上面的分析,此题就变的很简单了。
N个顶点连通至少需要N-1条边,这个是学计算机的都晓得的基础知识(树)。此问题总需要的最少边为total = N-1,每连接两个不在同一集合中的顶点时,所需要的边数减一(--total),ok了,最后连完之后的total就是还需要的边数(也是现在的等价类数目),这个应该也很好理解。
程序实现:
#include <stdio.h> int total; int pre[1001]; void init(int n){ int i; for(i=1;i<=n;++i){ pre[i] = i; } } int root(int x){ if(x!=pre[x]){ pre[x] = root(pre[x]); } return pre[x]; } void merge(int a,int b){ int x = root(a); int y = root(b); if(x!=y){ pre[x]=y; --total; } } int main(){ int N,M,i,st,end; while(scanf("%d",&N) && N){ scanf("%d",&M); init(N); total = N-1; for(i=0;i<M;++i){ scanf("%d %d",&st,&end); merge(st,end); } printf("%d\n",total); } return 0; }
这段代码就很好理解了。到此结束了。