并查集

简介: 并查集

常见两种操作:

第一种方法:

合并两个集合(代码效率不高)



/

merge1(a,b)
{
  i=min(a,b);
  j=max(a,b);
  for(i=0;i<=N;i++)
  {
  if(set[k]==j)
  {
    set[k]=i;
  }
  }
 }


对数组的所有元素进行遍历一边,查找数组元素是否为6,若是6,则将数组元素改写为2

查找某元素属于哪个集合

findl(x)
{
  return set[x];
}


第二种方法:(树)


合并两个集合

直接将领导a归附于领导b即可

merge2(a,b)
{
  set[a]=b;
}


/


查找某元素属于哪个集合(效率不高)

find2(x)
{
  r=x;
  while(set[r]!=r)
  {
  r=set[r];
  return r;
  }
}


/

优化后的算法:

查找:

解释:每个集合中最小的为树的根,每个节点的父节点是领导(不是最高领导,只是直属领导)



/

find2(x)
{
  r=x;
  while(set[r]!=r)
  {
  r=set[r];
  return r;
  }
}


合并:

merge3(a,b)
{
  if(height(a)==height(b))
  {
  height(a)==height(a)+1;
  set[b]=a;
  }else if(height(a)<height(b))
  {
  set[a]=b;
  }else 
  {
  set[b]=a;
  }
}


解释:树高的做领导,方框格格里面的(数组元素)用于装着领导


相关文章
|
7月前
|
算法
并查集,路径压缩
并查集,路径压缩
48 0
|
7月前
并查集。。
并查集。。
39 0
并查集及其应用
并查集及其应用
69 0
|
7月前
|
机器学习/深度学习
并查集(UnionFind)总结
并查集(UnionFind)总结
73 0
|
存储 算法 iOS开发
并查集详解及应用
并查集详解及应用
3854 0
|
存储 Python
【23. 并查集】
**用途**: - 将俩个集合合并 - 询问俩个元素是否在一个集合当中 **基本原理**: - 每个集合用一棵树来表示。树根的编号就是整个集合的编号,每个节点存储它的父节点,`p[x]`表示x的父节点。
124 0
【23. 并查集】