十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
十年的黑河网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同,自动调整黑河建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联从事“黑河网站设计”,“黑河网站推广”以来,每个客户项目都认真落实执行。这篇文章将为大家详细讲解有关C++利用map实现并查集的方法,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
并查集(Union-Find)是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。 并查集存在两个操作(1.Union 联合 2.finddeputy 查找代表结点) 和一个需要解答的问题( issameset 是否 在一个集合中,或者说是否有同一个代表结点)。
利用map实现主要通过两个map的对象 ,一个map类型的fathermap,关键字为子结点,值为其父结点(父结点不一定就是代表结点),当我们需要查找两个两个元素是否在一个集合中时,只需一直向上找(函数finddupty),在找的过程中,会压缩路径,把沿途经过的结点直接挂在其代表结点下,看是否有共同的代表结点;
一个map类型的sizemap,key为结点,value为其子结点的个数(这个个数只对代表结点有效,子结点无效),主要用处是在合并(union)时将子结点较少的代表结点挂在子结点代表较多的代表结点下,且sizemap中父结点对应的value要加上子结点较少的代表的结点个数。
代码如下:
#include