并查集[讲义].ppt

并查集[讲义].ppt

《并查集[讲义].ppt》由会员分享，可在线阅读，更多相关《并查集[讲义].ppt（76页珍藏版）》请在冰点文库上搜索。

并查集初步及应用并查集初步及应用引例：

犯罪团伙引例：

犯罪团伙11、最小生成树、最小生成树22、细胞个数、细胞个数33、房间问题、房间问题（noi94）（noi94）44、代码等式、代码等式55、银河英雄传说、银河英雄传说（noi2002）（noi2002）并查集的概念及运算并查集的概念及运算内容：

内容：

引例：

引例：

【犯罪团伙犯罪团伙】警察抓到了警察抓到了nn个罪犯，警察根据经验知个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。

有可能一个伙的成员之间直接或间接认识。

有可能一个犯罪团伙只有一个人。

犯罪团伙只有一个人。

请你根据已知罪犯之间的关系，确定犯请你根据已知罪犯之间的关系，确定犯罪团伙的数量。

已知罪犯的编号从罪团伙的数量。

已知罪犯的编号从11至至nn。

输入：

输入：

第一行：

第一行：

nn（=10000,=10000,罪犯数量），罪犯数量），第二行：

第二行：

mm（=100000=100000，关系数量），关系数量）以下若干行：

每行两个数：

以下若干行：

每行两个数：

II和和jj，中间一，中间一个空格隔开，表示罪犯个空格隔开，表示罪犯ii和罪犯和罪犯jj相互认识。

相互认识。

输出：

一个整数，犯罪团伙的数量。

输出：

一个整数，犯罪团伙的数量。

输入：

输入：

118124534135671051089输出：

输出：

3测试数据说明：

测试数据说明：

1s共共10个测试数据：

个测试数据：

（1）5个数据：

个数据：

n=1000,m=n=9000,100000=m=90000;建立无向图的模型。

建立无向图的模型。

如果如果x和和y认识，结点认识，结点x和和y建立一条无向边。

建立一条无向边。

求无向图的连通分量（求无向图的连通分量（dfs;bfs）时间和空和空间！

邻接矩阵：

空间太大，超时。

邻接矩阵：

空间太大，超时。

邻接表：

空间满足，时间查过邻接表：

空间满足，时间查过1s1s最容易想到的算法：

最容易想到的算法：

抽象的算法：

抽象的算法：

开始把开始把nn个人看成个人看成nn个独立集合。

个独立集合。

每读入两个有联系的人每读入两个有联系的人ii和和jj，查找，查找ii和和jj所在的所在的集合集合pp和和qq，如果，如果pp和和qq是同一个集合，不作处理；是同一个集合，不作处理；如果如果pp和和qq属于不同的集合，则合并属于不同的集合，则合并pp和和qq为一个为一个集合。

集合。

最后统计集合的个数即可得到问题的解。

最后统计集合的个数即可得到问题的解。

需要将需要将nn个不同的元素划分成一组不相交的集个不同的元素划分成一组不相交的集合。

开始时，每个元素自己成一个单元素集合，合。

开始时，每个元素自己成一个单元素集合，然后按照一定的顺序或问题给定的条件和要求将然后按照一定的顺序或问题给定的条件和要求将属于同一组元素（有特定关系）所在的集合合并，属于同一组元素（有特定关系）所在的集合合并，最后统计集合的个数往往就是问题的解。

最后统计集合的个数往往就是问题的解。

在这个过程中要反复的用到在这个过程中要反复的用到查询查询某个元素属某个元素属于哪个集合的运算；两个不同集合于哪个集合的运算；两个不同集合合并合并的运算。

的运算。

适合描述这类问题的抽象数据结构类型称为并查适合描述这类问题的抽象数据结构类型称为并查集（合并与查找）。

集（合并与查找）。

一类问题模型：

一类问题模型：

并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些不相交集合不相交集合不相交集合不相交集合S=S1,S2,S=S1,S2,SnSn,每个集合每个集合SiSi都都有一个特殊元素有一个特殊元素rootSirootSi,称为集合的代表元称为集合的代表元.并查集支持三种操作：

并查集支持三种操作：

InitInit（XX）:

集合初始化：

把元素集合初始化：

把元素xixi加到集合加到集合SiSi中。

每个中。

每个集合集合SiSi只有一个独立的元素只有一个独立的元素xi,xi,并且元素并且元素xixi就是集合就是集合SiSi的的代表元素。

代表元素。

Find（xFind（x）:

）:

查找：

查找查找：

查找xixi所在集合所在集合SiSi的代表的代表rootSirootSi。

优化：

路径压缩。

优化：

路径压缩。

Union（xUnion（x,y）:

y）:

合并：

合并：

把把xx和和yy所在的两个不同集合合并。

所在的两个不同集合合并。

并查集的一个重要的应用是确定给定集合上的并查集的一个重要的应用是确定给定集合上的等价等价关系的个数。

关系的个数。

等价关系是一个具有自反、对称和传递三个性质的等价关系是一个具有自反、对称和传递三个性质的关系。

关系。

等号等号“=”在实数集合在实数集合R上是一个等价关系。

上是一个等价关系。

对于实数中的任意对于实数中的任意x、y、z。

一定满足下列关系：

。

一定满足下列关系：

1）、）、x=x（自反性）（自反性）2）、如果）、如果x=y，则，则y=x（对称性）（对称性）3）、如果）、如果x=y，y=z，则，则x=z（传递性）（传递性）【犯罪团伙犯罪团伙】问题：

问题：

“同一团伙同一团伙“抽象成无向图的抽象成无向图的”连通连通”连通连通”可以看成可以看成nn个人的集合上的一个等价关系。

个人的集合上的一个等价关系。

对于图中的任意对于图中的任意33个顶点：

个顶点：

A,B,CA,B,C。

有：

。

有：

11）、）、AA连通连通A.A.（自反性）（自反性）22）、如果）、如果AA连通连通BB，则，则BB连通连通A.A.（对称性）（对称性）33）、如果）、如果AA连通连通BB，BB连通连通CC，则，则AA连通连通C.C.（传递性）（传递性）一个连通分量就是一个等价关系（连通），等价关系的一个连通分量就是一个等价关系（连通），等价关系的个数就是连通分量的个数。

个数就是连通分量的个数。

一个等价关系对应一个集合。

一个等价关系对应一个集合。

一个集团对应一个集合。

一个集团对应一个集合。

并查集的树型结构实现并查集的树型结构实现采用树型结构实现并查集的基本思想是：

采用树型结构实现并查集的基本思想是：

每个子集合用一棵树来表示。

树中的每个结每个子集合用一棵树来表示。

树中的每个结点用于存放集合中的一个元素。

点用于存放集合中的一个元素。

树中的每个结点树中的每个结点x设置一个指向父亲的指针。

设置一个指向父亲的指针。

fatherx用根结点的元素代表该树所表示的集合。

用根结点的元素代表该树所表示的集合。

Init（X）:

集合初始化：

集合初始化：

fatherxi=0（或者或者xi）;每个结点都是一颗独立的树，每个结点都是一颗独立的树，是该树的代表元素。

是该树的代表元素。

三种操作：

三种操作：

Find（x）:

查找：

查找：

查找查找x所在集合所在集合Si的代表的代表rootSi。

即：

查找即：

查找x所在树的树根结点（代表元素）。

所在树的树根结点（代表元素）。

顺着顺着x往上找，直到找到根节点，也就确定了往上找，直到找到根节点，也就确定了x所在的集合。

所在的集合。

Union（x,y）:

合并合并x和和y所在的不同集合。

所在的不同集合。

p=find（x）；q=find（y）;ifpqthenfatherp=q或或fatherq=p2131145610798输入：

输入：

1181245341356710510891121634510798初始化初始化:

合并合并:

树根（集合代表元素）：

树根（集合代表元素）：

Father1=0;father8=0;father11=0孩子结点：

孩子结点：

father2=1;father4=3;father5=4;father9=8查找：

查找：

find（5）=1find（7）=1find（9）=8find（11）=11find

（1）=1find（8）=8合并：

合并：

union（x，y）union（5，9）p=find（5）=1;q=find（9）=8;fatherq=p;或或fatherp=qfather8=1;father1=8算法的算法的实现：

实现：

aiai：

为结点：

为结点ii的父亲指针。

的父亲指针。

初始值为初始值为00，表示是树根。

每个结点看成一颗树。

，表示是树根。

每个结点看成一颗树。

每读入两个结点每读入两个结点xx，yy，找，找xx的树根的树根pp，令，令p=p=find（xfind（x）;）;找找yy的树根的树根qq，令，令q=q=find（yfind（y）;）;如果如果p=qp=q，不做处理；如果属，不做处理；如果属于不同的两棵树即：

于不同的两棵树即：

pqpq，则合并两棵树，则合并两棵树.具体操作是：

具体操作是：

把把pp看作看作qq的孩子或者把的孩子或者把qq看作看作pp的的孩子孩子:

apap=q=q或者或者aqaq=p=p最后统计树的数量，即最后统计树的数量，即aiai=0=0的结点的数量的结点的数量,即问题即问题的解：

犯罪集团的个数。

的解：

犯罪集团的个数。

【犯罪团伙犯罪团伙】问题：

问题：

输入：

输入：

118124534135671051089constmax=10000;vara:

array1.maxoflongint;/父亲指针父亲指针i,j,m,n,ans,x,y,p,q:

longint;functionfind（i:

longint）:

longint;非递归算法找非递归算法找i的根的根varj,k,t:

longint;beginj:

=i;/顺着结点顺着结点i开始向上找，直到根为止。

开始向上找，直到根为止。

whileaj0doj:

=aj;find:

=j;end;begin程序算法：

程序算法：

readln（n）;/读入顶点数读入顶点数readln（m）;/读入关系：

边读入关系：

边fillchar（a,sizeof（a）,0）;默认根标志是默认根标志是0，开始全是树根，开始全是树根fori:

=1tomdobeginreadln（x,y）;p:

=find（x）;查找查找x的根的根q:

=find（y）;查找查找y的根的根ifpqthenaq:

=p;合并合并p和和q子树子树end;ans:

=0;树根记数树根记数fori:

=1tondoifai=0theninc（ans）;记录树根结点记录树根结点writeln（ans）;end.functionfind（i:

longint）:

longint;/递归算法找递归算法找i的根的根varj,k,t:

longint;beginifai=0thenexit（i）;/若若i为根，返回本身结点序号为根，返回本身结点序号find:

=find（ai）;/否则继续向上找否则继续向上找end;Find（i）递归算法递归算法改进运行时间的两种启发式策略：

改进运行时间的两种启发式策略：

11、按秩合并、按秩合并秩秩=树的高度树的高度高度小的树的根指高度向大树的根。

减少整个树的高度，高度小的树的根指高度向大树的根。

减少整个树的高度，提高查找效率。

提高查找效率。

22、路径压缩、路径压缩根据等价关系的传递性，该变树的结构，使树变得扁平，根据等价关系的传递性，该变树的结构，使树变得扁平，从而提高查找效率。

从而提高查找效率。

Union（2，1）Union（3，2）Union（3，4）Union（n，n-1）Find

（1）Find

（2）Find（n）n1n-12.213n-1n按秩合并按秩合并N次查找总代价次查找总代价=n*（n+1）/2=（n2）O（nlgn）按秩合并按秩合并路径压缩路径压缩:

查找查找find（ifind（i）时进行时进行路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便把路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点这样可以减小以后的查这样可以减小以后的查找次数找次数实现路径压缩的简单非递归算法：

从结点到根走两遍：

第一实现路径压缩的简单非递归算法：

从结点到根走两遍：

第一遍找根；第二遍是将路径上的所有结点的父亲都设为根。

遍找根；第二遍是将路径上的所有结点的父亲都设为根。

Union（5,10）树越扁平查找效率越高。

树越扁平查找效率越高。

路径压缩程序：

路径压缩程序：

非递归算法：

非递归算法：

functionfind（i:

longint）:

longint;非递归算法找非递归算法找i的根的根varj,k,t:

longint;beginj:

=i;whileaj0doj:

=aj;/顺着顺着i向上找根。

向上找根。

find:

=j;k:

=i;从从i开始对子树结点进行路径压缩开始对子树结点进行路径压缩whileak0dobegint:

=k;k:

=ak;at:

=j;end;end;functionfunctionfind（i:

longint）:

longintfind（i:

longint）:

longint;采用递归算法：

寻找结点采用递归算法：

寻找结点ii的树根，并对结点的树根，并对结点ii所在的子树所在的子树进行路径压缩，返回调整后的进行路径压缩，返回调整后的ii的父指针（根）的父指针（根）beginbeginififaiai=0then=0thenexit（iexit（i）;）;若若ii为根，返回本身结点序号为根，返回本身结点序号find:

=find:

=find（aifind（ai）;）;递归找根结点递归找根结点aiai:

=find;:

=find;路径压缩：

找到根后，按原路返回的同时，进行路径压缩：

找到根后，按原路返回的同时，进行中间结点的逆序路径压缩，一次性完成中间结点的逆序路径压缩，一次性完成end;end;递归算法（多采用此法）：

递归算法（多采用此法）：

ifaai=0thenexit（ai）;若若i的父结点为根，则返回父结点的父结点为根，则返回父结点constmax=10000;vara:

array1.maxoflongint;i,j,m,n,sum,x,y,p,q:

longint;functionfind（i:

longint）:

longint;beginifai=0thenexit（I）;ifaai=0thenexit（ai）;find:

=find（ai）;ai:

=find;end;proceduremain;beginfillchar（a,sizeof（a）,0）;readln（n）;readln（m）;fori:

=1tomdobeginreadln（x,y）;p:

=find（x）;q:

=find（y）;ifpqthenaq:

=p;end;sum:

=0;fori:

=1tondoifai=0theninc（sumend;procedureprint;beginwriteln（sum）;end;BEGINmain;print;END.完整程序完整程序并查集的时间复杂度并查集的时间复杂度l其中其中（n）是是Ackermann函数的某个反函数，增长速度及函数的某个反函数，增长速度及其缓慢。

其缓慢。

（n）=4。

所以并查集的单次查找操作的时间复。

所以并查集的单次查找操作的时间复杂度也几乎是常数级的。

杂度也几乎是常数级的。

按秩合并：

时间：

按秩合并：

时间：

O（mO（m*lg（nlg（n）路径压缩：

最坏路径压缩：

最坏:

O（n+lg（nO（n+lg（n））按秩合并和路径压缩：

按秩合并和路径压缩：

O（mO（m（n）（n）经过启发式合并和路径压缩之后的并查集，执行经过启发式合并和路径压缩之后的并查集，执行mm次查找的复杂度为次查找的复杂度为O（mO（m（n）（n）；算法导论算法导论p312p312（犯罪集团：

（犯罪集团：

m=100000m=100000）n个元素的个元素的m次不相交集合操作次不相交集合操作例例1最小生成树最小生成树用并查集实现用并查集实现kruskalkruskal算法算法算法步骤：

算法步骤：

11、把图中的边按权值从小到大排序。

、把图中的边按权值从小到大排序。

22、按从小到大的顺序依次向树中加边。

、按从小到大的顺序依次向树中加边。

在添加每一条边（在添加每一条边（uu，vv）时，如果）时，如果uu和和VV两个点两个点分分分分别属于不同的两个集合别属于不同的两个集合别属于不同的两个集合别属于不同的两个集合（即两个点还没有连通，不在即两个点还没有连通，不在即两个点还没有连通，不在即两个点还没有连通，不在同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环），那么就加入这条，那么就加入这条，那么就加入这条，那么就加入这条边，否则处理下一条边。

边，否则处理下一条边。

边，否则处理下一条边。

边，否则处理下一条边。

33、直到添加、直到添加n-1n-1条边。

条边。

1243517301024723512345Kruskal算法算法;sort;/排序边排序边fori:

=1tondofi:

=0;/初始化根为初始化根为0ans:

=0;/价值价值fori:

=1tomdounion（ei）;/加边加边procedureunion（p:

node）;/检查边检查边p是否能加到生成树中是否能加到生成树中varx,y:

integer;beginx:

=find（p.u）;/找找u的根的根y:

=find（p.v）;/找找v的根的根ifxythen/不同根，构不成环，加入到树中不同根，构不成环，加入到树中begininc（ans,p.data）;fy:

=x;/根合并根合并end;end;functionfind（i:

integer）:

integer;/查找查找i的父亲的父亲beginiffi=0thenexit（i）;/i是根是根ifffi=0thenexit（fi）;/i的父亲是根的父亲是根find:

=find（fi）;/递归查找递归查找fi:

=find;/路径压缩路径压缩end;一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

如阵列:

0234500067103456050020456006710000000089有4个细胞。

输入：

输入：

整数m,n（m行，n列=3000）M*n的矩阵，数据之间无空格；输出：

输出：

细胞的个数。

例例2、细胞统计、细胞统计0234500067103456050020456006710000000089算法分析：

算法分析：

l搜索可以实现（搜索可以实现（dfs，bfs）dx:

array1.4ofinteger=（1,0,-1,0）;dy:

array1.4ofinteger=（0,1,0,-1）;/逐行逐列扫描：

逐行逐列扫描：

ans:

=0;fori:

=1tondoforj:

=1tomdoifbi,jthenbegininc（ans）;try（i,j）;end;proceduretry（i,j:

integer）;/dfsvark:

integer;beginbi,j:

=false;/访问标记访问标记fork:

=1to4doifbi+dxk,j+dykthentry（i+dxk,j+dyk）;end;l并查集实现并查集实现C（i-1,j）B（i,j-1）A（i,j）逐行扫描，依次处理每一个点逐行扫描，依次处理每一个点初始化：

每个点的父亲指向本身初始化：

每个点的父亲指向本身/每个数是独立的一个细胞每个数是独立的一个细胞处理点处理点A（I,j）:

3种情况如下：

种情况如下：

如果如果B和和C都是细胞：

合并都是细胞：

合并P=find（c）;q=find（b）;Ifpqthenfatherp=qfatherA=q;如果如果B是而是而C不是，则不是，则fatherA=B或或fatherA=find（B）如果如果B不是而不是而C是，则是，则fatherA=C或或fatherA=find（C）统计父亲是自身统计父亲是自身（find（i）=i）的结点数即细胞的个数的结点数即细胞的个数constmaxn=3000;typepoint=recordx,y:

integer;/行与列end;a:

array1.maxn,1.maxnofpoint;/父亲结点b:

array0.maxn,0.maxnofboolean;/是否是细胞算法的实现：

算法的实现：

/数据读入数据读入readln（n,m）;fori:

=1tondobeginforj:

=1tomdobeginread（ch）;bi,j:

=ch0;ifbi,jthenbeginai,j.x:

=i;ai,j.y:

=j;end;/初始化父亲指向自身初始化父亲指向自身end;readln;end;fori:

=1tondoforj:

=1tomdoifbi,jthenbeginifbi-1,jandbi,j-1then/左与上是细胞beginp:

=find（i-1,j）;q:

=find（i,j-1）;if（p.xq.x）or（p.yq.y）thenap.x,p.y:

=q;ai,j:

=q;end;ifbi-1,jandnotbi,j-1then/上是左不是beginai,j.x:

=i-1;ai,j.y:

=j;end;ifbi,j-1andnotbi-1,jthen/上不是左是beginai,j.x:

=i;ai,j.y:

=j-1;end;end;逐行扫描处理每个细胞结点逐行扫描处理每个细胞结点functionfind（x0,y0:

longint）:

point;/查找当前位置（x0，y0）细胞的父亲结点beginif（x0=ax0,y0.x）and（y0=ax0,y0.y）thenexit（ax0,y0）;find:

=find（ax0,y0.x,ax0,y0.y）;ax0,y0:

=find;/路径压缩end;/统计细胞的个数：

父亲指向自己的结点数量统计细胞的个数：

父亲指向自己的结点数量tot:

=0;fori:

=1tondoforj:

=1tomdoif（ai,j.x=i）and（ai,j.y=j）theninc（tot）;例例3、房间问题（、房间问题（NOI94）下图是一张建筑平面图，编程计算下图是一张建筑平面图，编程计算1、该建筑中有多少个房间；、该建筑中有多少个房间；2、最大的房间有多大；、最大的房间有多大；3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。

指出该墙。

、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。

指出该墙。

该建筑分成该建筑分成个方块（个方块（m50，n50），每个方块可有），每个方块可有04堵墙堵墙（0表示无墙）。

表示无墙）。

输入数据：

输入数据：

用一个数字表示一个方块。

用一个数字表示一个方块。

文件开始是北南方向的方块数，其次是东西方向的方块数。

文件开始是北南方向的方块数，其次是东西方向的方块数。

后面的行中，每个方块中墙的特征由数字后面的行中，每个方块中墙的特征由数字P来描述（来描述（0P15）。

数字）。

数字P是下面是下面的可能取的数字之和：

的可能取的数字之和：

1（西墙（西墙west）2（北墙（北墙north）4（东