当前位置:   article > 正文

并查集(Disjoint Set Union,DSU)

有路径压缩的dsu也需要rank吗

定义:

并查集是一种用来管理元素分组情况的数据结构。

作用:

查询元素a和元素b是否属于同一组

合并元素a和元素b所在的组

优化方法:

1.路径压缩

2.添加高度属性

拓展延伸:

分组并查集

带权并查集

代码如下:

  1. //带有路径压缩的并查集
  2. //一句话并查集(常用)
  3. int dsu(int x){
  4. return x==par[x]?x:(par[x]=dsu(par[x]));
  5. }
  6. //带有路径压缩和高度的并查集
  7. //ranks[i]代表以i为根的树的最大高度,若不存在则为0
  8. int rank[maxn];
  9. int par[maxn];
  10. void init(int n){
  11. for(int i=0;i<n;i++){
  12. par[i]=i;
  13. rank[i]=0;
  14. }
  15. }
  16. int dsu(int x){
  17. if(par[x]==x){
  18. return x;
  19. }else{
  20. return par[x]=dsu(par[x]);
  21. }
  22. }
  23. void union(int x,int y){
  24. int fx=dsu(x);
  25. int fy=dsu(y);
  26. if(fx==fy){
  27. return;
  28. }
  29. if(rank[fx]<rank[fy]){
  30. par[fx]=fy;
  31. }else if(rank[fx]>rank[fy]){
  32. par[fy]=fx;
  33. }else{
  34. par[fy]=fx;
  35. rank[fx]++;
  36. }
  37. }
  38. bool same(int x,int y){
  39. return dsu(x)==dsu(y);
  40. }
  41. poj1182 食物链
  42. //带权并查集解法
  43. /*
  44. 模仿矢量计算来处理权值
  45. 当我们知道x与祖先x1的关系,y与祖先y1的关系,x与y的关系时,求x1与y1的关系时,使用矢量
  46. 计算:
  47. x1->x ->y ->y1
  48. */
  49. #include<cstdio>
  50. #include<cstring>
  51. #include<algorithm>
  52. using namespace std;
  53. const int maxn=50010;
  54. int par[maxn],ran[maxn];
  55. int dsu(int x){
  56. if(x==par[x]){
  57. return x;
  58. }else{
  59. int fx=dsu(par[x]);
  60. //一开始将par[x]写成了fx,一直wa
  61. //如果是fx,那么每一次都到最终的根节点,求解ran数组显然不正确
  62. ran[x]=(ran[x]+ran[par[x]]+3)%3;
  63. par[x]=fx;
  64. return par[x];
  65. }
  66. }
  67. int main()
  68. {
  69. int n,m;
  70. int ty,x,y,ans=0;
  71. scanf("%d%d",&n,&m);
  72. for(int i=0;i<=n;i++){
  73. par[i]=i;
  74. ran[i]=0;
  75. }
  76. while(m--){
  77. scanf("%d%d%d",&ty,&x,&y);
  78. if(x==y&&ty==2){
  79. ans++;
  80. }
  81. else if(x>n||y>n){
  82. ans++;
  83. }
  84. else{
  85. int fx=dsu(x);
  86. int fy=dsu(y);
  87. if(fx==fy)
  88. {
  89. if((ran[x]-ran[y]+3)%3!=ty-1){
  90. ans++;
  91. //这里如果不相等,说明这句话是错误的,continue
  92. //一开始因为没写continue,一直wa
  93. continue;
  94. }
  95. }
  96. par[fx]=fy;
  97. ran[fx]=(-ran[x]+ty-1+ran[y]+3)%3;
  98. }
  99. }
  100. printf("%d\n",ans);
  101. return 0;
  102. }
  103. //分组并查集解法
  104. /*
  105. 个人理解带权并查集就是多个并查集,
  106. 然后一个set所代表的的关系不仅一种,
  107. 所以对每个元素要用多重表示,在这个题目里
  108. 就是+i*n来区分每个元素和另一些元素的不同关系
  109. */
  110. #include<iostream>
  111. #include<string>
  112. #include<algorithm>
  113. #include<cstdio>
  114. #include<cstring>
  115. #include<cmath>
  116. using namespace std;
  117. const int maxn = 200000+10;
  118. int par[maxn];
  119. int dsu(int x){
  120. return x==par[x]?x:(par[x]=dsu(par[x]));
  121. }
  122. bool same(int x,int y){
  123. return dsu(x)==dsu(y);
  124. }
  125. int main(){
  126. int n,m;
  127. scanf("%d%d",&n,&m);
  128. for(int i=0;i<=3*n;i++){
  129. par[i]=i;
  130. }
  131. int cnt=0;
  132. int x,y,ty;
  133. while(m--){
  134. scanf("%d%d%d",&ty,&x,&y);
  135. if(x<=0||x>n||y<=0||y>n){
  136. cnt++;
  137. continue;
  138. }
  139. if(ty==1){
  140. if(same(x,y+n)||same(y,x+n)){
  141. cnt++;
  142. }else{
  143. for(int i=0;i<3;i++){
  144. int fx=dsu(x+i*n);
  145. int fy=dsu(y+i*n);
  146. par[fx]=fy;
  147. }
  148. }
  149. }else{
  150. if(x==y||same(x,y)||same(y,x+n)){
  151. cnt++;
  152. }else{
  153. for(int i=0;i<3;i++){
  154. int fx=dsu(x+i*n);
  155. int fy=dsu(y+(i+1)%3*n);
  156. par[fx]=fy;
  157. }
  158. }
  159. }
  160. }
  161. printf("%d\n",cnt);
  162. return 0;
  163. }

  

 

  

转载于:https://www.cnblogs.com/imzscilovecode/p/8646143.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/792362
推荐阅读
相关标签
  

闽ICP备14008679号