第五节 并查集.

Presentation on theme: "第五节 并查集."— Presentation transcript:

1 第五节 并查集

2 引入 在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内竞赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往超过了空间的限制，计算机无法承受；即使在空间上能勉强通过，运行的时间复杂度也极高，根本不可能在比赛规定的运行时间内计算出试题需要的结果，只能采用一种特殊数据结构——并查集来描述。

3 引例 【例4-9】、亲戚(relation) 【问题描述】
或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。 【输入格式】 输入由两部分组成。 第一部分以N，M开始。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤ )，每行有两个数ai, bi，表示已知ai和bi是亲戚。 第二部分以Q开始。以下Q行有Q个询问(1≤Q≤ )，每行为ci, di，表示询问ci和di是否为亲戚。

4 引例 【输出格式】 对于每个询问ci, di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。 【输入样例】 10 7
　　10 7 　　2 4 　　5 7 　　1 3 　　8 9 　　1 2 　　5 6 　　2 3 　　3 　　3 4 　　7 10 【输出样例】 　　Yes 　　No

5 引例 【算法分析】 将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个N个顶点M条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通块中。 　　用传统的思路，可以马上反应过来，对于输入的N个点M条边，找出连通块，然后进行判断。但这种实现思路首先必须保存M条边，然后再进行普通的遍历算法，效率显然不高。再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成： 　　　第一行是N，M。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤ )，每行有三个数ki,ai, bi。ai, bi表示两个元素，ki为0或1，ki为1时表示这是一条边的信息，即ai, bi是亲戚关系；ki为0时表示是一个提问，根据此行以前所得到的信息，判断ai, bi是否亲戚，对于每条提问回答Yes或者No。 这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要表示人与人之间的关系。

6 引例 用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图1： 输入关系 分离集合 初始状态 {1}{2}{3}{4}{5}{6}{7}{8}{9}{10} (2,4) {1}{2,4}{3}{5}{6}{7}{8}{9}{10} (5,7) {1}{2,4}{3}{5,7}{6}{8}{9}{10} (1,3) {1,3}{2,4}{5,7}{6}{8}{9}{10} (8,9) {1,3}{2,4}{5,7}{6}{8,9}{10} (1,2) {1,2,3,4}{5,7}{6}{8,9}{10} (5,6) {1,2,3,4}{5,6,7}{8,9}{10} (2,3) {1,2,3,4}{5,6,7}{8,9}{10} 图1 　　由图1可以看出，操作是在集合的基础上进行的，没有必要保存所有的边， 而且每一步得到的划分方式是动态的。 　　那么，如何来实现以上的算法思想呢？我们就用到并查集。

7 并查集的基本思想 1、什么叫并查集 　　并查集（union-find set）是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。 　　例如，有这样的问题：初始时n个元素分属不同的n个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。 　 并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，数组实现、链表实现和树实现。一般用的比较多的是数组实现。

8 并查集的基本思想 2、并查集支持的操作 并查集的数据结构记录了一组分离的动态集合S={S1,S2,…,Sk}。每个集合通过一个代表加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的答案应该是相同的。 动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现需要支持如下操作： 　　MAKE(x)：建立一个新的集合，其仅有的成员（同时就是代表）是x。由于各集合是分离的，要求x没有在其它集合中出现过。 　　UNIONN(x,y)：将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是Sx∪Sy的某个成员。一般来说，在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。此后，由新的集合S代替了原来的Sx和Sy。 FIND(x)：返回一个指向包含x的集合的代表。

9 并查集的基本思想 对于引例的问题，我们可以运用并查集简单地进行如下做法： ⑴、元素的合并图示： 1 2 3 4 5 ① 合并1和2
② 合并1和3 ③ 合并5和4 5 1 1 1 2 3 2 3 4 2 ④ 合并3和5 1 用father[i]表示元素i的父亲结点，进行不断并到不同的集合中 2 3 5 4

10 并查集的基本思想 ⑵、再对输入的数据进行判断：是否在同一集合。 具体程序如下： #include<iostream>
　　#include<cstdio> 　　using namespace std; 　　#define maxn 20001 　　int father[maxn]; 　　int m,n,i,x,y,q; 　　/* 　　int find(int x) //用非递归的实现 　　{ 　　 while (father[x] != x) x = father[x]; 　　 return x; 　　} 　　*/ 　　int find(int x) //用递归的实现 　　 if (father[x] != x) return find(father[x]); 　　 else return x; 　　}　　 　　void unionn(int r1,int r2) 　　 father[r2] = r1;

11 并查集的基本思想 int main() { freopen("relation.in","r",stdin);
　　{ 　　 freopen("relation.in","r",stdin); 　　 freopen("relation.out","w",stdout); 　　 cin >> n >> m; 　　 for (i = 1; i <= n; i++) 　　 father[i] = i; //建立新的集合，其仅有的成员是i 　　 for (i = 1; i <= m; i++) 　　 { 　　 scanf("%d%d",&x,&y); 　　 int r1 = find(x); 　　 int r2 = find(y); 　　 if (r1 != r2) unionn(r1,r2); 　　 } 　　 cin >> q; 　　 for (i = 1; i <= q; i++) 　　 if (find(x) == find(y)) printf("Yes\n"); 　　 else printf("No\n"); 　　 return 0; 　　} 　　以上做法当数据比较特殊的时候，比如一条单链老长，数据这种“并”与“查”的方式肯定会超时。

12 并查集的基本思想 ⑶、下面有一种优化的方法： 并查集的路径压缩
　　此种做法就是将元素的父亲结点指来指去地指，当这棵树是链的时候，可见判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。 　　路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。 　　这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向根节点1，如图： 1 2 3 5 4 由此我们得到了一个复杂度几乎为常数的算法。 【程序清单】 （1）初始化： 　for (i = 1; i <= n; i++) father[i] = i; 　因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。

13 并查集的基本思想 （2）寻找根结点编号并压缩路径： int find (int x) {
　　{ 　　 if (father[x] != x) father[x] = find (father[x]); 　　 return father[x]; 　　} （3）合并两个集合： void unionn(int x,int y) { 　　x = find(x);y = find(y); 　　father[y] = x; } （4）判断元素是否属于同一集合： bool judge(int x,int y) x = find(x); y = find(y); if (x == y) return true; else return false; 这个的引题已经完全阐述了并查集的基本操作和作用。

14 并查集的基本思想 优化的具体程序如下: #include<iostream> #include<cstdio>
　　using namespace std; 　　#define maxn 20001 　　int father[maxn]; 　　int m,n,i,x,y,q; 　　/* 　　int find(int x) //用非递归的实现 　　{ 　　 while (father[x] != x) x= father[x]; 　　 return x; 　　} 　　*/ 　　int find(int x) //用递归的实现 　　 if (father[x] != x) father[x] = find(father[x]); //路径压缩 　　 return father[x]; 　　void unionn(int r1,int r2) 　　 father[r2] = r1;

15 并查集的基本思想 int main() { freopen("relation.in","r",stdin);
　　{ 　　 freopen("relation.in","r",stdin); 　　 freopen("relation.out","w",stdout); 　　 cin >> n >> m; 　　 for (i = 1; i <= n; i++) 　　 father[i] = i; //建立新的集合，其仅有的成员是i 　　 for (i = 1; i <= m; i++) 　　 { 　　 scanf("%d%d",&x,&y); 　　 int r1 = find(x); 　　 int r2 = find(y); 　　 if (r1 != r2) unionn(r1,r2); 　　 } 　　 cin >> q; 　　 for (i = 1; i <= q; i++) 　　 scanf("%d%d",&x,&y);; 　　 if (find(x) == find(y)) printf("Yes\n"); 　　 else printf("No\n"); 　　 return 0; 　　} 这种做法就可能不会超时了

16 并查集的基本思想 【例4-8】格子游戏 【问题描述】
　　Alice和Bob玩了一个古老的游戏：首先画一个n * n的点阵（下图n = 3） 　　接着，他们两个轮流在相邻的点之间画上红边和蓝边： 直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了(n <= 200)，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？ 【输入格式】 　　输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行，每行首先有两个数字(x, y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是"D "，则是向下连一条边，如果是"R "就是向右连一条边。输入数据不会有重复的边且保证正确。 【输出格式】 　　输出一行：在第几步的时候结束。假如m步之后也没有结束，则输出一行“draw”。 【输入样例】 　　3 5 　　1 1 D 　　1 1 R 　　1 2 D 　　2 1 R 　　2 2 D 【输出样例】 　　4

17 并查集的基本思想 【参考程序】 #include <iostream> using namespace std;
struct node { int x,y;}f[301][301],k1,k2; int i,j,m,n,x,y; char c; node root(node k) { if((f[k.x][k.y].x==k.x)&&(f[k.x][k.y].y==k.y))return k; f[k.x][k.y]=root(f[k.x][k.y]); return f[k.x][k.y]; } int main() cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) {f[i][j].x=i;f[i][j].y=j;}

18 并查集的基本思想 for(i=1;i<=m;i++) { cin>>x>>y>>c;
if(c=='D') {k1=root(f[x][y]);k2=root(f[x+1][y]);} if(c=='R') {k1=root(f[x][y]);k2=root(f[x][y+1]);} if((k1.x==k2.x)&&(k1.y==k2.y)) {cout<<i<<endl;return 0;} else f[k1.x][k1.y]=k2; } cout<<"draw"<<endl; return 0;

19 其他 三、求无向图的连通分量 这个问题其实在例4-7中已经提过了。这里再单独提出来强调一下，因为求无向图连通分量是个非常常用的算法。通过并查集可以使得空间上省去对边的保存，同时时间效率又是很高的。 　　需要特别指出的是，如果用链表来实现的话，最后任何在同一个集合（即连通块）中的元素，其代表指针的值都是相等的。而采用有根树来实现的话，算法结束后，留下的依然是树的关系，因此如果希望每个元素都指向它的根的话，还需要对每个节点进行一次find操作，这样每个节点的父节点都是代表此集合的节点。在某些统计问题中，往往需要这样做。 四、Kruskal最小生成树算法 此经典算法的思想是将树上的边按照边权排序，然后从小到大分析每一条边，如果选到一条边e=(v1,v2),且v1和v2不在一个连通块中，就将e作为最小生成树的一条边，否则忽略e。这其中明显就包含了并查集的算法。Kruskal算法也只有在结合了并查集后才能说是个高效的算法。 五、小结 　　总之在解决某些特定的问题时，并查集往往能够发挥出重要的作用，大家一定要熟悉这种算法，能举一反三。

20 上机练习 1、团伙(group) 时间限制 2S 【问题描述】 在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友； 　　所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？ 【输入格式】group.in 　　第1行为n和m，1<n<1000,1<=m<= ； 　　以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。 【输出格式】group.out 　　一个整数，表示这n个人最多可能有几个团伙。 【输入样例】 　　6 4 　　1 1 4 　　0 3 5 　　0 4 6 　　1 1 2 【输出样例】 　　3

21 上机练习 2、打击犯罪(black) 【问题描述】
　　某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度唯一由集团内的犯罪团伙数量确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。 【输入格式】black.in 　　第一行一个正整数n。接下来的n行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第i行存在正整数k，表示i，k两个团伙可以直接联系。 【输出格式】black.out 　　一个正整数，为k的最小值

22 上机练习 【样例输入】 7 2 2 5 2 2 4 2 2 3 2 5 7 2 5 6 【样例输出】 　　1 【提示】 输出1（打击掉红色团伙）

23 上机练习 3、家谱(gen) 时间限制 2S 【问题描述】
现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。 【输入格式】gen.in 　　输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。 【输出格式】gen.out 　　按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

24 上机练习 【输入样例】 #George +Rodney #Arthur +Gareth +Walter #Gareth +Edward
$ 【输出样例】 Edward Arthur Walter Arthur Rodney George Arthur Arthur