临沂网站建设昂牛网络,wordpress 文件发送邮件,怎么在本地安装网站,在线响应式网站一#xff1a;并查集的相关知识
这道题用到了并查集#xff0c;所以我就学了一下并查集#xff0c;所以把自己的见解也分享给大家#xff08;建议 先看视频 再浏览 博客 再自己敲一遍 学习效率高而已#xff0c;我总是乱着来 以为看几篇博客就会了#xff0c;其实最后还…一并查集的相关知识
这道题用到了并查集所以我就学了一下并查集所以把自己的见解也分享给大家建议 先看视频 再浏览 博客 再自己敲一遍 学习效率高而已我总是乱着来 以为看几篇博客就会了其实最后还是老老实实 去B站看大佬讲解视频 才搞懂
1:并查集
并查集是一种树型的数据结构 用于处理一些不相交集合Disjoint Sets的合并及查询问题 1查询元素a和元素b是否属于同一组 2合并元素a和元素b所在组 将有相同元素的元素 合并为一个组 3需要初始化一个数组存放父节点其索引值 代表元素
2并查集的AC代码模板
/*并查集是一种树型的数据结构用于处理一些不相交集合Disjoint Sets的合并及查询问题1查询元素a和元素b是否属于同一组2合并元素a和元素b所在组 将有相同元素的元素 合并为一个组 3需要初始化一个数组存放父节点其索引值 代表元素
*/#includebits/stdc.h
using namespace std;int father[100]; int find( int x){while( x ! father[x] ){x father[x];}return x;
} void merge(int x,int y)
{int a find(x);//x的根节点为a int b find(y);//y的根节点为bif( a ! b )father[b] a;//那么将b的根节点 设为 a }int main()
{//初始化 我们将每一个结点的前导结点设置为自己//如果在merge函数时未能形成连通将独立成点for( int i 0; i 10; i ){father[i] i;}}上方的find函数 效率不高当处理大数据时使用并查集查找时如果查找次数很多那么使用朴素版的查找方式肯定要超时。比如有一百万个元素每次都从第一百万个开始找这样一次运算就是106如果程序要求查找个一千万次这样下来就是1013,肯定要出问题的。
所以有了压缩路径的算法就是一棵树只有叶节点
int find( int a ){int ra;while(Father[r]!r)rFather[r]; //找到他的前导结点int ia,j;while(i!r){ //路径压缩算法jFather[i]; //记录x的前导结点Father[i]r; //将i的前导结点设置为r根节点ij;}return r;
}如有疑问 请留言 加油陌生的你
