首页 > 代码库 > 并查集
并查集
并查集是用来管理元素分组情况的数据结构。
就是将所有的点都是 自己属于一类,与别人没有关系 ,自己的父节点是自己;
查找的是自己最上面的节点是谁,也就是说,自己属于哪一类;
并查集可以高效的进行如下操作。
- 查询元素a和元素b是否属于同一组。
- 合并元素a和元素b所在的组。
并查集不能进行分割操作。
并查集的实现就是三个函数
- 初始化
- 合并
- 查寻
在树形结构中都存在退化的现象,为了让并查集避免退化我们记录了树的高度,在合并的时候我们将高度低的树加入到高度高的树上。
我们还用了路径压缩(好厉害的名字) 其实就是
从图中可以很清晰的看明白。
现在我们来写构造并查集的代码
第一个初始化:
void init(int x) { for(int i=0;i<=x;i++) { par[i]=i; ran[i]=0; } }
就是将所有的点都是 自己属于一类,与别人没有关系 ,自己的父节点是自己;
接下来是查找函数
int find(int x) { if(par[x]==x) return x; else return par[x]=find(par[x]); }
查找的是自己最上面的节点是谁,也就是说,自己属于哪一类;
最后我们来附上最牛掰的 合并函数:
void unite(int x,int y) { int xx = find(x); int yy = find(y); if(xx==yy)//先找出父节点 如果相同就返回; return ; if(ran[x]>ran[y])//如果不相同就把矮的树加到高的树上,如果相同就直接把一颗加到另一颗上; par[y]=x; else if(ran[y]>ran[x]) par[x]=y; else { par[y]=x; ran[x]++; } }
好了 到这我们的并查集就基本结束了。
好了感谢自己坚持
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。