并查集
2018-06-17 23:50:43来源:未知 阅读 ()
在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。
如果n比较大,那么反复询问你某个元素所在集合,你该怎么做?
如果每次都遍历,那么显然会超时,那么用一些数据结构比如建树什么的,很可能会空间不够,在这个时候就得用到并查集了。
顾名思义,并查集就是将相同集合的想办法联系在一起,那样查的时候就不用一一遍历来询问它是不是这个集合的了。
例题,畅通工程,大体题意:每行给你俩个数代表路的编号且这俩条路已联通,最后问你还至少需要修几条路使所有路都能够联通。
思路:给每一个联通的集团设定一个老大,而集团成员都存储老大的id,每进来俩相连的成员看他们老大是谁,如果是不同老大就改成相同老大,因为他们是相连的,是一个集团的,那最后看看有多少个老大,那就有多少个集团,那就需要多少条路将这些集团连起来。
若要这些集团连起来,只需一个集团的某一个和其他集团有联系就好了,看看实际操作代码吧:
int f[MAX+1]; //申请一个数组存储每个成员的老大id
for(int i=1;i<=MAX;i++)
f[i]=i; //初始化每个人的老大就是自己 初始化
int _find(int n) //寻找这个人的老大是谁
{ if(n!=f[n])
return _find(f[n]); 查询
return n;
}
a=_find(a1); b=_find(b1); //新进来俩有联系的成员,分别查询他们老大是谁
if(a!=b) //如果这俩人老大不同,分别属于俩集团的 联通
{f[a]=b; //让一方老大任另一方老大为老大,俩集团从此有联系,合并成一个集团,有共同的一个老大了
//_find(a); } //下面压缩路径时加这句进行压缩
int sum=0; 回答题目问题
for(int i=1;i<=MAX;i++) //sum为现在有几个老大,即有几个集团,当然统一局面就是所有人都有一个老大,他们都存储自己上司id,而老大自己存储自己id。
if(f[i]==i)
sum++;
如果要问这俩人是不是一个集团的,直接看他俩老大是不是同一个人。(_find(a)?_find(b))
这样就是并查集的查询,联通,都搞定了。
当然我说的这么简单是没有压缩过路径的,就是所有人都存自己上司的id,寻找老大时需要由上司再问上司,直到老大(老大的特点是存储自己id),而压缩过路径的就是人们都存它老大的id,问的时候直接看俩人存储的id是否相同(f[a]?f[b])。
压缩路径得加这段代码,很容易看懂的,就在寻找函数上加点就好了:
int _find(int n)
{ int res=n;
while(n!=f[n])
n=f[n]; //找到老大id
int j;
while(res!=n)
{ j=f[res];
f[res]=n; //把从自己开始把上司id都改成老大id
res=j;}
return n; //返回老大
}
待续……
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++11 之 并发编程 (一)
下一篇:快速幂+大数取模
- C++ 一些术语 2020-05-22
- 关于使用ffmpeg的一些牢骚 2020-05-08
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
- 【图论】几个例题~ 2020-04-14
- 加边的无向图--并查集 2020-04-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash