现在的位置: 首页 > 综合 > 正文

并查集学习（5）

2013年08月12日 ⁄ 综合 ⁄ 共 7419字 ⁄ 字号 小 中 大 ⁄ 评论关闭
最近学习了并查集、线段树、树状数组以及RMQ(Range Minimum Query)这几种关于快速查找
的数据结构和算法，并做了一些ACM的题目巩固了一下。准备写一下总结。
本次总结一下并查集：
并查集对解决不相交集合的合并查找操作非常有效，主要提供了一下几个方法：
make_set(x) 把每一个元素初始化为一个集合
find_set(x) 查找一个元素所在的集合
union_set(x,y) 合并x,y所在的两个集合
空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，
这里Alpha是Ackerman函数的某个反函数，在很大的范围内这个函数的值可以看成是不大于4的，所以并
查集的操作可以看作是线性的。
并查集针对不同的问题有两种不同的实现：
第一种：
make_set(x)的时候parent[x] = x,也就是根的parent指向自己，以此来判断这个元素是否为根元素，
rank值记录树的高度，合并的时候尽量让小的合并到大的集合上，这样可以减少数的高度。
代码如下：
Cpp代码 复制代码
  1. int parent[50001];   
  2. int rank[50001];   
  3.   
  4. void make_set(int x){   
  5.     parent[x] = x;   
  6.     rank[x] = 0;   
  7. }   
  8.   
  9. //查找的时候，进行路径压缩parent[x] = find_set(parent[x]),   
  10. //把查找路径上的结点都指向跟结点，减小树的高度   
  11. int find_set(int x){   
  12.     if(x != parent[x]) parent[x] = find_set(parent[x]);   
  13.     return parent[x];   
  14. }   
  15.   
  16. void union_set(int x,int y){   
  17.     int r1 = find_set(x);   
  18.     int r2 = find_set(y);   
  19.     if(r1 == r2) return;//如果两个元素在相同的集合中，直接retun;   
  20.   
  21.     if(rank[r1] < rank[r2]//把rank值较小的集合合并到达的集合中   
  22.         parent[r2] = r1;   
  23.     else{   
  24.         if(rank[r1] == rank[r2])//两个rank值相等的树合并后rank要增加一   
  25.             rank[r2] += 1;   
  26.         parent[r1] = r2;   
  27.     }   
  28. }  

第二种：
make_set的时候把parent[x] = -1，根节点parent记录了该集合元素个数
的相反数,所以这种方法很适合想知道某个元素所在的集合的个数的情况。

Cpp代码 复制代码
  1. int parent[30001];   
  2.   
  3. void make_set(int x){   
  4.     parent[x] = -1;   
  5. }   
  6.   
  7. int find_set(int x){   
  8.     int p = x;   
  9.     while(parent[p] > 0) p = parent[p];//找到跟结点   
  10.     while(x != p){//查找并压缩路径，让查找路径上的每一个x的parent[x] = p,p为根节点   
  11.         int temp = parent[x];   
  12.         parent[x] = p;   
  13.         x = temp;   
  14.     }   
  15.     return x;   
  16. }   
  17.   
  18. void union_set(int x,int y){   
  19.     int r1 = find_set(x);   
  20.     int r2 = find_set(y);   
  21.   
  22.     if(r1 == r2) return;   
  23.     if(parent[r1] < parent[r2]){//集合小的合并到集合大的上，并更新集合元素个数的计数   
  24.         parent[r1] += parent[r2];   
  25.         parent[r2] = r1;   
  26.     }else{   
  27.         parent[r2] += parent[r1];   
  28.         parent[r1] = r2;   
  29.     }   
  30. }  

以下是这两种并查集的两道ACM应用，可以巩固一下学习的知识：
poj2524 http://acm.pku.edu.cn/JudgeOnline/problem?id=2524
这道题目的主要意思是：n个大学生，指出m对宗教信仰相同的学生，然后让你估算这n个学生中最多
有多少种宗教信仰。
这道题很简单，把宗教数初始化为学生数n,对给出的每对大学生i,j，如果他们在不同的集合，那么
就合并，然后宗教的数量减一
以下是AC的代码：

Cpp代码 复制代码
  1. #include<iostream>   
  2. using namespace std;   
  3.   
  4. int parent[50001];   
  5. int rank[50001];   
  6.   
  7. void make_set(int x){   
  8.     parent[x] = x;   
  9.     rank[x] = 0;   
  10. }   
  11.   
  12. int find_set(int x){   
  13.     if(x != parent[x]) parent[x] = find_set(parent[x]);   
  14.     return parent[x];   
  15. }   
  16.   
  17. void union_set(int x,int y){   
  18.     int r1 = find_set(x);   
  19.     int r2 = find_set(y);   
  20.     if(r1 == r2) return;   
  21.   
  22.     if(rank[r1] < rank[r2])   
  23.         parent[r2] = r1;   
  24.     else{   
  25.         if(rank[r1] == rank[r2])   
  26.             rank[r2] += 1;   
  27.         parent[r1] = r2;   
  28.     }   
  29. }   
  30.   
  31. int main(){   
  32.     int m,n;   
  33.     int ncases = 0;   
  34.     int i = 0;   
  35.     while(cin >> n >> m, n){   
  36.         int a,b;   
  37.         ++ncases;   
  38.         for(i = 0; i < n; i++){   
  39.             make_set(i);       
  40.         }   
  41.   
  42.         for(i = 0; i < m; i++){   
  43.             cin >> a >> b;   
  44.             int x = find_set(a);   
  45.             int y = find_set(b);   
  46.             if(x != y){//不同的集合，合并并减一   
  47.                 n--;   
  48.                 union_set(x,y);   
  49.             }   
  50.         }   
  51.         cout << "Case " << ncases << ": " << n << endl;   
  52.     }   
  53.     return 0;   
  54. }  

poj 1611 The Suspects http://acm.pku.edu.cn/JudgeOnline/problem?id=1611
这道题的意思是有一种传染病SARS，学生有很多的groups,如果groups的一个学生是疑似患者Suspect，
则整个组的其他人都是Suspects,但一个人可能属于不同的组，初始0是suspect,问学生中有多少个
Suspects.
这个题目很简单，把同一组的人进行合并，然后查找一个0元素所在集合元素的个数，由于要统计一个
集合元素的个数，所以使用第二种构造并查集的方法。
AC的代码：

Cpp代码 复制代码
  1. #include<iostream>   
  2. using namespace std;   
  3.   
  4. int parent[30001];   
  5.   
  6. void make_set(int x){   
  7.     parent[x] = -1;   
  8. }   
  9.   
  10. int find_set(int x){   
  11.     int p = x;   
  12.     while(parent[p] > 0) p = parent[p];   
  13.     while(x != p){   
  14.         int temp = parent[x];   
  15.         parent[x] = p;   
  16.         x = temp;   
  17.     }   
  18.     return x;   
  19. }   
  20.   
  21. void union_set(int x,int y){   
  22.     int r1 = find_set(x);   
  23.     int r2 = find_set(y);   
  24.   
  25.     if(r1 == r2) return;   
  26.     if(parent[r1] < parent[r2]){   
  27.         parent[r1] += parent[r2];   
  28.         parent[r2] = r1;   
  29.     }else{   
  30.         parent[r2] += parent[r1];   
  31.         parent[r1] = r2;   
  32.     }   
  33. }   
  34.   
  35. int main(){   
  36.     int n,m,i = 0;   
  37.     while(cin >> n >> m, n){   
  38.         for(i = 0; i < n; i++){   
  39.             make_set(i);   
  40.         }   
  41.   
  42.         for(i = 0; i < m; i++){   
  43.             int k;   
  44.             cin >> k;   
  45.             int first_s,s;   
  46.             cin >> first_s;   
  47.             for(int j = 1; j < k; j++){   
  48.                 cin >> s;   
  49.                 union_set(first_s,s);   
  50.             }   
  51.         }   
  52.         cout << -parent[find_set(0)] << endl;   
  53.     }   
  54.     return 0;   
  55. }  

其他来自fandy_wang总结中提供的一些相关题目：
POJ 1182 食物链
并查集的拓展注意: 只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C，这三类动物的食物链
构成了有趣的环形。A吃B， B吃C，C吃A。也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女，只有:男-〉女，女-〉男满足，否则，找到同性恋，结束程序。
法二:二分图匹配
法三:并查集的拓展:和1182很像，只不过这里就有两组，而1182是三组,1611无限制
POJ 1861 Network == zju_1542    并查集+自定义排序+贪心求"最小生成树"
答案不唯一，不过在ZOJ上用QSORT()和SORT()都能过，在POJ上只有SORT()才能过...
POJ 1703 Find them, Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像，就是把代码稍微修改了一下就AC了！
注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是说只有两个组。
POJ 2236 Wireless Network        并查集的应用
需要注意的地方：1、并查集；2、N的范围，可以等于1001；3、从N+1行开始，第一个输入的可以是字符串。
POJ 1988 Cube Stacking            并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样；2、增加了一个数组behind[x],记录战舰x在列中的相对位置；3、详细解题报告见银河英雄传说。
JOJ 1905 Freckles   == POJ 2560 最小生成树
法一：Prim算法；法二：并查集实现Kruskar算法求最小生成树
JOJ 1966 Super Market III == PKU 1456 Supermarket 带限制的作业排序问题（贪心+并查集）
提高题目：
POJ 2912 Rochambeau
POJ 1733 Parity game   
POJ 1308 Is It A Tree?

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞