2024-11-27 00:12 哈尔滨理工大学 C++ 发布于黑龙江
关注
关于并查集的三种优化
声明：三种方法几乎没法同时优化，特定题目要求保留树结构，无法使用路径压缩。
1.路径压缩o（1）复杂度
只需要查根的时候直接指向根
int root (int x)
{
return fa[x]=fa[x]==x?x:root(fa[x]);
}
2.按秩合并（深度）
初始化都为一
int d[N];
for()
rnk[i]=1;
merge操作中，
if(rnk[x]>rnk[y])swap(x,y);
pre[x]=y;
if(rnk[x]==rnk[y])rnk++;
3.启发式合并（大小）
初始化同上；
if(sz[x]>sz[y])
swap(x,y);
pre[x]=y;
sz[y]+=sz[x];
1.路径压缩o（1）复杂度
只需要查根的时候直接指向根
int root (int x)
{
return fa[x]=fa[x]==x?x:root(fa[x]);
}
2.按秩合并（深度）
初始化都为一
int d[N];
for()
rnk[i]=1;
merge操作中，
if(rnk[x]>rnk[y])swap(x,y);
pre[x]=y;
if(rnk[x]==rnk[y])rnk++;
3.启发式合并（大小）
初始化同上；
if(sz[x]>sz[y])
swap(x,y);
pre[x]=y;
sz[y]+=sz[x];
全部评论
相关推荐
点赞 评论 收藏
分享
新。。。：不到100人的cto不就跟普通的+1ld管的人数量差不多吗 点赞 评论 收藏
分享
查看11道真题和解析 点赞 评论 收藏
分享
