并查集[讲义].ppt

1、并查集初步及应用并查集初步及应用引例：犯罪团伙引例：犯罪团伙1 1、最小生成树、最小生成树2 2、细胞个数、细胞个数3 3、房间问题、房间问题(noi94)(noi94)4 4、代码等式、代码等式5 5、银河英雄传说、银河英雄传说(noi2002)(noi2002)并查集的概念及运算并查集的概念及运算内容：内容：引例：引例：【犯罪团伙犯罪团伙】警察抓到了警察抓到了n n个罪犯，警察根据经验知个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一

2、犯罪团的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从罪团伙的数量。已知罪犯的编号从1 1至至n n。输入：输入：第一行：第一行：n n（=10000,=10000,罪犯数量），罪犯数量），第二行：第二行：m m（=100000=100000，关系数量），关系数量）以下若干行：每行两个数：以下若干行：每行两个数：I I 和和j j，中间一，中间一个空格隔开，表示罪犯个空格隔开，表示罪犯i i和

3、罪犯和罪犯j j相互认识。相互认识。输出：一个整数，犯罪团伙的数量。输出：一个整数，犯罪团伙的数量。输入：输入：118 1 24 53 41 35 67 105 108 9输出：输出：3测试数据说明：测试数据说明：1 s共共10个测试数据：个测试数据：（1）5个数据：个数据：n=1000,m=n=9000,100000=m=90000;建立无向图的模型。建立无向图的模型。如果如果x和和y认识，结点认识，结点x和和y建立一条无向边。建立一条无向边。求无向图的连通分量（求无向图的连通分量（dfs;bfs）时间和空和空间！邻接矩阵：空间太大，超时。邻接矩阵：空间太大，超时。邻接表：空间满足，时间查过

4、邻接表：空间满足，时间查过1s1s最容易想到的算法：最容易想到的算法：抽象的算法：抽象的算法：开始把开始把n n个人看成个人看成n n个独立集合。个独立集合。每读入两个有联系的人每读入两个有联系的人i i和和j j，查找，查找i i和和j j所在的所在的集合集合p p和和q q，如果，如果p p和和q q是同一个集合，不作处理；是同一个集合，不作处理；如果如果p p和和q q属于不同的集合，则合并属于不同的集合，则合并p p和和q q为一个为一个集合。集合。最后统计集合的个数即可得到问题的解。最后统计集合的个数即可得到问题的解。需要将需要将n n个不同的元素划分成一组不相交的集个不同的元素划分

5、成一组不相交的集合。开始时，每个元素自己成一个单元素集合，合。开始时，每个元素自己成一个单元素集合，然后按照一定的顺序或问题给定的条件和要求将然后按照一定的顺序或问题给定的条件和要求将属于同一组元素（有特定关系）所在的集合合并，属于同一组元素（有特定关系）所在的集合合并，最后统计集合的个数往往就是问题的解。最后统计集合的个数往往就是问题的解。在这个过程中要反复的用到在这个过程中要反复的用到查询查询某个元素属某个元素属于哪个集合的运算；两个不同集合于哪个集合的运算；两个不同集合合并合并的运算。的运算。适合描述这类问题的抽象数据结构类型称为并查适合描述这类问题的抽象数据结构类型称为并查集（合并与查

6、找）。集（合并与查找）。一类问题模型：一类问题模型：并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些并查集是一种树型的数据结构，用于处理一些不相交集合不相交集合不相交集合不相交集合S=S1,S2,S=S1,S2,SnSn,每个集合每个集合SiSi都都有一个特殊元素有一个特殊元素rootSirootSi,称为集合的代表元称为集合的代表元.并查集支持三种操作：并查集支持三种操作：InitInit（X X）:集合初始化：把元素集合初始化：把元素xixi加到集合加到集合SiSi中。每个中。每个集合集合SiSi只有一个独立的元素只有

7、一个独立的元素xi,xi,并且元素并且元素xixi就是集合就是集合SiSi的的代表元素。代表元素。Find(xFind(x):):查找：查找查找：查找xixi所在集合所在集合SiSi的代表的代表rootSirootSi。优化：路径压缩。优化：路径压缩。Union(xUnion(x,y):,y):合并：合并：把把x x和和y y所在的两个不同集合合并。所在的两个不同集合合并。并查集的一个重要的应用是确定给定集合上的并查集的一个重要的应用是确定给定集合上的等价等价关系的个数。关系的个数。等价关系是一个具有自反、对称和传递三个性质的等价关系是一个具有自反、对称和传递三个性质的关系。关系。等号等号“=

8、”在实数集合在实数集合R上是一个等价关系。上是一个等价关系。对于实数中的任意对于实数中的任意x、y、z。一定满足下列关系：。一定满足下列关系：1）、）、x=x（自反性）（自反性）2）、如果）、如果x=y，则，则y=x（对称性）（对称性）3）、如果）、如果x=y，y=z，则，则x=z（传递性）（传递性）【犯罪团伙犯罪团伙】问题：问题：“同一团伙同一团伙“抽象成无向图的抽象成无向图的”连通连通”连通连通”可以看成可以看成n n个人的集合上的一个等价关系。个人的集合上的一个等价关系。对于图中的任意对于图中的任意3 3个顶点：个顶点：A,B,CA,B,C。有：。有：1 1）、）、A A连通连通A.A.

9、（自反性）（自反性）2 2）、如果）、如果A A连通连通B B，则，则B B连通连通A.A.（对称性）（对称性）3 3）、如果）、如果A A连通连通B B，B B连通连通C C，则，则A A连通连通C.C.（传递性）（传递性）一个连通分量就是一个等价关系（连通），等价关系的一个连通分量就是一个等价关系（连通），等价关系的个数就是连通分量的个数。个数就是连通分量的个数。一个等价关系对应一个集合。一个等价关系对应一个集合。一个集团对应一个集合。一个集团对应一个集合。并查集的树型结构实现并查集的树型结构实现采用树型结构实现并查集的基本思想是：采用树型结构实现并查集的基本思想是：每个子集合用一棵树来表

10、示。树中的每个结每个子集合用一棵树来表示。树中的每个结点用于存放集合中的一个元素。点用于存放集合中的一个元素。树中的每个结点树中的每个结点x设置一个指向父亲的指针。设置一个指向父亲的指针。fatherx 用根结点的元素代表该树所表示的集合。用根结点的元素代表该树所表示的集合。Init（X）:集合初始化：集合初始化：fatherxi=0(或者或者xi);每个结点都是一颗独立的树，每个结点都是一颗独立的树，是该树的代表元素。是该树的代表元素。三种操作：三种操作：Find(x):查找：查找：查找查找x所在集合所在集合Si的代表的代表rootSi。即：查找即：查找x所在树的树根结点（代表元素）。所在树

11、的树根结点（代表元素）。顺着顺着x往上找，直到找到根节点，也就确定了往上找，直到找到根节点，也就确定了x所在的集合。所在的集合。Union(x,y):合并合并x和和y所在的不同集合。所在的不同集合。p=find(x)；q=find(y);if pq then fatherp=q 或或 fatherq=p2131145610798输入：输入：118 1 24 53 41 35 67 105 108 91121634510798初始化初始化:合并合并:树根（集合代表元素）：树根（集合代表元素）：Father1=0;father8=0;father11=0孩子结点：孩子结点：father2=1;fa

12、ther4=3;father5=4;father9=8查找：查找：find(5)=1 find(7)=1 find(9)=8 find(11)=11 find(1)=1 find(8)=8合并：合并：union（x，y）union（5，9）p=find(5)=1;q=find(9)=8;fatherq=p;或或 fatherp=q father8=1;father1=8算法的算法的 实现：实现：aiai：为结点：为结点i i的父亲指针。的父亲指针。初始值为初始值为0 0，表示是树根。每个结点看成一颗树。，表示是树根。每个结点看成一颗树。每读入两个结点每读入两个结点x x，y y，找，找x x的

13、树根的树根p p，令，令p=p=find(xfind(x););找找y y的树根的树根q q，令，令q=q=find(yfind(y););如果如果p=qp=q，不做处理；如果属，不做处理；如果属于不同的两棵树即：于不同的两棵树即：pqpq，则合并两棵树，则合并两棵树.具体操作是：具体操作是：把把p p看作看作q q的孩子或者把的孩子或者把q q看作看作p p的的孩子孩子:apap=q=q或者或者aqaq=p=p最后统计树的数量，即最后统计树的数量，即aiai=0=0的结点的数量的结点的数量,即问题即问题的解：犯罪集团的个数。的解：犯罪集团的个数。【犯罪团伙犯罪团伙】问题：问题：输入：输入：1

14、18 1 24 53 41 35 67 105 108 9const max=10000;var a:array1.maxof longint;/父亲指针父亲指针 i,j,m,n,ans,x,y,p,q:longint;function find(i:longint):longint;非递归算法找非递归算法找i的根的根 var j,k,t:longint;begin j:=i;/顺着结点顺着结点i开始向上找，直到根为止。开始向上找，直到根为止。while aj0 do j:=aj;find:=j;end;begin程序算法：程序算法：readln(n);/读入顶点数读入顶点数 readln(m

15、);/读入关系：边读入关系：边 fillchar(a,sizeof(a),0);默认根标志是默认根标志是0，开始全是树根，开始全是树根 for i:=1 to m do begin readln(x,y);p:=find(x);查找查找x的根的根 q:=find(y);查找查找y的根的根 if pq then aq:=p;合并合并p和和q子树子树 end;ans:=0;树根记数树根记数 for i:=1 to n do if ai=0 then inc(ans);记录树根结点记录树根结点 writeln(ans);end.function find(i:longint):longint;/递归

16、算法找递归算法找i的根的根 var j,k,t:longint;begin if ai=0 then exit(i);/若若i为根，返回本身结点序号为根，返回本身结点序号 find:=find(ai);/否则继续向上找否则继续向上找 end;Find(i)递归算法递归算法改进运行时间的两种启发式策略：改进运行时间的两种启发式策略：1 1、按秩合并、按秩合并 秩秩=树的高度树的高度 高度小的树的根指高度向大树的根。减少整个树的高度，高度小的树的根指高度向大树的根。减少整个树的高度，提高查找效率。提高查找效率。2 2、路径压缩、路径压缩 根据等价关系的传递性，该变树的结构，使树变得扁平，根据等价关

17、系的传递性，该变树的结构，使树变得扁平，从而提高查找效率。从而提高查找效率。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)时进行时进行 路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便路径压缩实际上是在找完根结点之后，在回来的时候顺便把

18、路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点把路径上元素的父亲指针都指向根结点这样可以减小以后的查这样可以减小以后的查找次数找次数 实现路径压缩的简单非递归算法：从结点到根走两遍：第一实现路径压缩的简单非递归算法：从结点到根走两遍：第一遍找根；第二遍是将路径上的所有结点的父亲都设为根。遍找根；第二遍是将路径上的所有结点的父亲都设为根。Union(5,10)树越扁平查找效率越高。树越扁平查找效率越高。路径压缩程序：路径压缩程序：非递归算法：非递归算法：function find(i:longint):longint;非递归算法找非递归算法找

19、i的根的根 var j,k,t:longint;begin j:=i;while aj0 do j:=aj;/顺着顺着i向上找根。向上找根。find:=j;k:=i;从从i开始对子树结点进行路径压缩开始对子树结点进行路径压缩 while ak0 do begin t:=k;k:=ak;at:=j;end;end;function function find(i:longint):longintfind(i:longint):longint;采用递归算法：寻找结点采用递归算法：寻找结点i i的树根，并对结点的树根，并对结点i i所在的子树所在的子树进行路径压缩，返回调整后的进行路径压缩，返回调整

20、后的i i的父指针（根）的父指针（根）begin begin if if aiai=0 then=0 then exit(iexit(i););若若i i为根，返回本身结点序号为根，返回本身结点序号 find:=find:=find(aifind(ai););递归找根结点递归找根结点 aiai:=find;:=find;路径压缩：找到根后，按原路返回的同时，进行路径压缩：找到根后，按原路返回的同时，进行中间结点的逆序路径压缩，一次性完成中间结点的逆序路径压缩，一次性完成 end;end;递归算法（多采用此法）：递归算法（多采用此法）：if aai=0 then exit(ai);若若i的父结点

21、为根，则返回父结点的父结点为根，则返回父结点const max=10000;var a:array1.maxof longint;i,j,m,n,sum,x,y,p,q:longint;function find(i:longint):longint;begin if ai=0 then exit(I);if aai=0 then exit(ai);find:=find(ai);ai:=find;end;procedure main;begin fillchar(a,sizeof(a),0);readln(n);readln(m);for i:=1 to m do begin readln(x

22、,y);p:=find(x);q:=find(y);if pq then aq:=p;end;sum:=0;for i:=1 to n do if ai=0 then inc(sum end;procedure print;begin writeln(sum);end;BEGIN main;print;END.完整程序完整程序并查集的时间复杂度并查集的时间复杂度l其中其中(n)是是Ackermann函数的某个反函数，增长速度及函数的某个反函数，增长速度及其缓慢。其缓慢。(n)=4。所以并查集的单次查找操作的时间复。所以并查集的单次查找操作的时间复杂度也几乎是常数级的。杂度也几乎是常数级的。按秩

23、合并：时间：按秩合并：时间：O(mO(m*lg(nlg(n)路径压缩：最坏路径压缩：最坏:O(n+lg(nO(n+lg(n)）按秩合并和路径压缩：按秩合并和路径压缩：O(mO(m(n)(n)经过启发式合并和路径压缩之后的并查集，执行经过启发式合并和路径压缩之后的并查集，执行m m次查找的复杂度为次查找的复杂度为O(mO(m(n)(n)；算法导论算法导论p312p312（犯罪集团：（犯罪集团：m=100000m=100000）n个元素的个元素的m次不相交集合操作次不相交集合操作例例1 最小生成树最小生成树用并查集实现用并查集实现kruskalkruskal算法算法算法步骤：算法步骤：1 1、把图

24、中的边按权值从小到大排序。、把图中的边按权值从小到大排序。2 2、按从小到大的顺序依次向树中加边。、按从小到大的顺序依次向树中加边。在添加每一条边（在添加每一条边（u u，v v）时，如果）时，如果u u和和V V两个点两个点分分分分别属于不同的两个集合别属于不同的两个集合别属于不同的两个集合别属于不同的两个集合(即两个点还没有连通，不在即两个点还没有连通，不在即两个点还没有连通，不在即两个点还没有连通，不在同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环同一棵树上，否则加上就构成环)，那么就加入这条，那么就加入这条，那么就加入这条，那么就加入这条边，否则处

25、理下一条边。边，否则处理下一条边。边，否则处理下一条边。边，否则处理下一条边。3 3、直到添加、直到添加n-1n-1条边。条边。1243517301024723512345Kruskal算法算法;sort;/排序边排序边 for i:=1 to n do fi:=0;/初始化根为初始化根为0 ans:=0;/价值价值 for i:=1 to m do union(ei);/加边加边procedure union(p:node);/检查边检查边p是否能加到生成树中是否能加到生成树中 var x,y:integer;begin x:=find(p.u);/找找u的根的根 y:=find(p.v);

26、/找找v的根的根 if xy then /不同根，构不成环，加入到树中不同根，构不成环，加入到树中 begin inc(ans,p.data);fy:=x;/根合并根合并 end;end;function find(i:integer):integer;/查找查找i的父亲的父亲 begin if fi=0 then exit(i);/i是根是根 if ffi=0 then exit(fi);/i的父亲是根的父亲是根 find:=find(fi);/递归查找递归查找 fi:=find;/路径压缩路径压缩 end;一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细

27、胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列:0234500067103456050020456006710000000089有4个细胞。输入：输入：整数m,n(m行，n列=3000)M*n的矩阵，数据之间无空格；输出：输出：细胞的个数。例例2、细胞统计、细胞统计0234500067103456050020456006710000000089算法分析：算法分析：l搜索可以实现（搜索可以实现（dfs，bfs）dx:array1.4of integer=(1,0,-1,0);dy:array1.4of integer=(0,1,0,-1);/逐行逐列扫描：逐行逐列扫描：ans:=0;for

28、 i:=1 to n do for j:=1 to m do if bi,j then begin inc(ans);try(i,j);end;procedure try(i,j:integer);/dfs var k:integer;begin bi,j:=false;/访问标记访问标记 for k:=1 to 4 do if bi+dxk,j+dyk then try(i+dxk,j+dyk);end;l并查集实现并查集实现C(i-1,j)B(i,j-1)A(i,j)逐行扫描，依次处理每一个点逐行扫描，依次处理每一个点 初始化：每个点的父亲指向本身初始化：每个点的父亲指向本身 /每个数是独

29、立的一个细胞每个数是独立的一个细胞 处理点处理点A(I,j):3种情况如下：种情况如下：如果如果B和和C都是细胞：合并都是细胞：合并 P=find(c);q=find(b);If pq then fatherp=q fatherA=q;如果如果B是而是而C不是，则不是，则 fatherA=B 或或fatherA=find(B)如果如果B不是而不是而C是，则是，则 fatherA=C 或或fatherA=find(C)统计父亲是自身统计父亲是自身(find(i)=i)的结点数即细胞的个数的结点数即细胞的个数const maxn=3000;type point=record x,y:integer

30、;/行与列 end;a:array1.maxn,1.maxnof point;/父亲结点 b:array0.maxn,0.maxnof boolean;/是否是细胞算法的实现：算法的实现：/数据读入数据读入 readln(n,m);for i:=1 to n do begin for j:=1 to m do begin read(ch);bi,j:=ch0;if bi,j then begin ai,j.x:=i;ai,j.y:=j;end;/初始化父亲指向自身初始化父亲指向自身 end;readln;end;for i:=1 to n do for j:=1 to m do if bi,j

31、 then begin if bi-1,j and bi,j-1 then /左与上是细胞 begin p:=find(i-1,j);q:=find(i,j-1);if(p.xq.x)or(p.yq.y)then ap.x,p.y:=q;ai,j:=q;end;if bi-1,jand not bi,j-1 then /上是左不是 begin ai,j.x:=i-1;ai,j.y:=j;end;if bi,j-1 and not bi-1,j then /上不是左是 begin ai,j.x:=i;ai,j.y:=j-1;end;end;逐行扫描处理每个细胞结点逐行扫描处理每个细胞结点func

32、tion find(x0,y0:longint):point;/查找当前位置（x0，y0）细胞的父亲结点 begin if(x0=ax0,y0.x)and(y0=ax0,y0.y)then exit(ax0,y0);find:=find(ax0,y0.x,ax0,y0.y);ax0,y0:=find;/路径压缩 end;/统计细胞的个数：父亲指向自己的结点数量统计细胞的个数：父亲指向自己的结点数量 tot:=0;for i:=1 to n do for j:=1 to m do if(ai,j.x=i)and(ai,j.y=j)then inc(tot);例例3、房间问题（、房间问题（NOI9

33、4）下图是一张建筑平面图，编程计算下图是一张建筑平面图，编程计算1、该建筑中有多少个房间；、该建筑中有多少个房间；2、最大的房间有多大；、最大的房间有多大；3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。该建筑分成该建筑分成个方块（个方块（m50，n50），每个方块可有），每个方块可有04堵墙堵墙（0表示无墙）。表示无墙）。输入数据：输入数据：用一个数字表示一个方块。用一个数字表示一个方块。文件开始是北南方向的方块数，其次是东西方向的方块数。文件开始是北南方向的方块数，其次是东西方向的方块数。后面的行中，每个方块中墙的特征由数字后面的行中，每个方块中墙的特征由数字P来描述（来描述（0P15）。数字）。数字P是下面是下面的可能取的数字之和：的可能取的数字之和：1（西墙（西墙 west）2（北墙（北墙 north）4（东