C++ 并查集模板

并查集一般在遇到求解冗余关系,关系合并,环的数量等问题的时候使用。不需要对各数值进行输出。

注意与有向无环图问题进行区分!

有向无环图模板看这里:https://blog.csdn.net/qq_41687938/article/details/117821723

 

并查集是一个很优美的数据结构,很多情况下,提炼问题后,可以用并查集进行解决,这里总结下并查集的模板及注释,可以直接用

1.并查集的使用:

//初始化并查集
int n = xx.size();
UnionFindSet dsu(n);//初始化并查集

//将两个点合并
for(int i = 0; i < n; i++){
    dsu.merge(xx[i], xx[i])
    //......
}

2.并查集模板(直接用就行,可以根据需要修改返回值出代码) 

有两处优化:(1)查询优化 (2)路径优化

//并查集实现
class UnionFindSet{
    vector<int> F;//并查集容器
    vector<int> rank;//秩优化(如果两个都有很多元素的根节点相遇,将根节点选为元素较少的那一个,可以节省时间)
    int n;

public:
    //并查集

目前已整理十万字的C/C++、嵌入式常见面试题!!!!还在持续更新中!!! 这个专栏写完了,再po上自己亲手敲的笔试编程题整理。

全部评论

相关推荐

牛客773130651号:巨佬,简历模板换成上下的,左右的很烦,hr看着不爽。。。科大随便乱杀,建议能保研就保研,不行也得考一下 ,985硕去干算法,比开发强多了。开发许多双非都能搞,学历优势用不上,算法有门槛
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务