【模板】并查集

前往:我自己搭建的博客

题目

洛谷P3367并查集

题解

并查集是一种支持合并与查询的数据结构。合并:如果要将元素a,b所在的两个集合合并,则将a所在集合的根节点作为b所在集合的根节点的子节点。一棵树上的所有节点属于同一个集合,根节点没有特殊意义,只是代表这个集合。 查询:如果想知道某个元素在哪个集合,就不断访问它的父节点,直到根节点。

[优化方法] 路径压缩:在查询过程中,将一路上的节点的父节点都改为根节点,减少以后查询的时间。 按秩合并:尽量减小树的深度,使得查询速度变快。但在路径压缩的前提下,这个优化的效果不明显。将深度小的数并到深度大的树上,使合并后的数深度小。也可以将深度改为集合内的元素个数,更加方便和实用。假设一个集合当前有x个元素,则将根节点的父节点设为 -x。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int n,m;
int fa[maxn];
int find(int x) {return fa[x]>0 ? fa[x]=find(fa[x]) : x;} //找x所在集合的根节点
inline void unite(int r1,int r2) //合并
{
fa[r1]>fa[r2] ? fa[r2]+=fa[r1],fa[r1]=r2 : (fa[r1]+=fa[r2],fa[r2]=r1);
} //注意这里要加括号,否则程序会将逗号前的内容当成一句完整的语句

int main()
{
memset(fa,-1,sizeof(fa));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int t,x,y; scanf("%d%d%d",&t,&x,&y);
int r1=find(x),r2=find(y);
if(t==1) {if(r1!=r2) unite(r1,r2);}
else if(r1==r2) printf("Y\n");
else printf("N\n");
}

return 0;
}

 

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【模板】并查集

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【模板】并查集
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏