重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

并查集浅析-创新互联

题目详情 - L2-024 部落 (pintia.cn)

十余年的蚌山网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整蚌山建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联从事“蚌山网站设计”,“蚌山网站推广”以来,每个客户项目都认真落实执行。

这里本人不对代码作解释,而是只对并查集作自我总结,这里本人随便写了一个测试用例,便于理解

算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)

我们输入两个数你n,m,然后输入m对数x,y,表示该两个数产生联系,求有几个独立的,也就是把产生联系的看作一个整体,而统计两两不产生联系的整体有几个。

下面是测试用例:

如下图应该输出的结果为3,表示3个整体互不相关,有联系的我们已经把他们挂在同一个根节点上,以根节点代表这一个整体,

这里上图比较简单,按理来说,是把 x当作y的父节点或者应当作x的父节点,最后挂到同一个根节点上,我们,通过函数体,去寻找他的根节点,以根节点的值作为一个整体的区别,根节点下的所有节点都等于根节点的值,因为我们令数组,a[i]=i,最后只要统计有几个a[i]=i就可以。

关键内容就是函数体和输入之后,利用函数将他们连接

#includeusing namespace std;
int a[10005];
int find(int x){
    if(a[x]!=x)a[x]=find(a[x]);
    return a[x];
}
int main(){
    int n,m,i,b=0,x,y;
   cin>>n>>m;
    for(i=1;i<=n;i++)a[i]=i;
    while(m--){
        cin>>x>>y;
        a[find(x)]=find(y);
    }
     for(i=1;i<=n;i++){
         if(a[i]==i)b++;
     }
    cout<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻标题:并查集浅析-创新互联
网页网址:http://cqcxhl.cn/article/dsjscd.html
在线咨询
服务热线
服务热线:028-86922220
TOP