Codeup 并查集之问题 B: 畅通工程

骑猪看日落 2023-02-14 02:25 10阅读 0赞

#### 分析 ####

我们可以把有道路能达到的两个城市看作一个连通块，那么题中要求的就是连通块的数量。  
假设有n个连通块，那么只需要在两个连通块间建一条路就可以满足要求，因此最后输出n-1就是要求的答案

转换到并查集中就是集合数-1

#include<iostream>
    using namespace std;
    int father[1010];
    bool isroot[1010];
    int cnt;
    void init()
    { 
        for(int i=1;i<1010;i++)
        { 
            father[i]=i;
            isroot[i]=false;
        }
        cnt=0;
    }
    int findfather(int a)
    { 
        int b=a;
        while(a!=father[a])//找根
        { 
            a=father[a];
        }
        //路径压缩
        while(b!=father[b])
        { 
            int c=b;
            b=father[b];
            father[c]=a;
        }
        return a;
    }
    void Union(int a,int b)//合并集合
    { 
        int faa=findfather(a);
        int fab=findfather(b);
        if(faa!=fab)
        { 
            father[faa]=fab;
        }
    }
    int main()
    { 
        int n,m;
        while(cin>>n)
        { 
            if(n==0)break;
            cin>>m;
            init();
            int a,b;
            for(int i=0;i<m;i++)
            { 
                cin>>a>>b;
                Union(a,b);
            }
            for(int i=1;i<=n;i++)//将根置为true
            { 
                isroot[findfather(i)]=true;
            }
            for(int i=1;i<=n;i++)
            { 
                if(isroot[i])cnt++;
            }
            cout<<cnt-1<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeup 并查集之问题 B: 畅通工程

分析我们可以把有道路能达到的两个城市看作一个连通块，那么题中要求的就是连通块的数量。假设有n个连通块，那么只需要在两个连通块间建一条路就可以满足要求，因此最后输出

骑猪看日落/ 2023年02月14日 02:25/ 0 赞/ 11 阅读

相关 Codeup 并查集之问题 A: 通信系统

思路：利用并查集建立起端点与端点的关系题目要求： 1.某个端点生成后，其余各个端点均能接收到消息这句话转换到并查集的思想就是所有的端点应该在一个集合之中

柔情只为你懂/ 2023年02月14日 02:11/ 0 赞/ 9 阅读

相关 hdoj 1232 畅通工程【并查集】

畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

た入场券/ 2022年08月04日 11:43/ 0 赞/ 173 阅读

相关畅通工程--hdu1232(并查集)

畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Love The Way You Lie/ 2022年08月04日 08:54/ 0 赞/ 197 阅读

相关 Hdu 1232 畅通工程（并查集水题）

题目：畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

拼搏现实的明天。/ 2022年06月10日 12:23/ 0 赞/ 173 阅读

相关畅通工程（并查集）

Problem Description 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以

た入场券/ 2022年06月06日 04:27/ 0 赞/ 161 阅读

相关 HDU 1233 还是畅通工程 (并查集)

include <bits/stdc++.h> using namespace std; const int maxn=10005; stru

╰半夏微凉°/ 2022年06月05日 01:57/ 0 赞/ 197 阅读

相关 HDU 1232 畅通工程 (并查集)

//题意不会度娘，用BOSS代替路 include <stdio.h> include <string.h> int a[1050];

偏执的太偏执、/ 2022年06月05日 01:55/ 0 赞/ 202 阅读

相关并查集-HDU 1232-畅通工程

并查集-HDU 1232-畅通工程 -------------------- 题目链接：[畅通工程][Link 1] 并查集基础： [数据

绝地灬酷狼/ 2022年05月15日 01:56/ 0 赞/ 247 阅读

相关 HDU-1232.畅通工程(并查集)

[HDU-1232.畅通工程][HDU-1232.] Problem Description 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连

港控/mmm°/ 2022年03月09日 05:58/ 0 赞/ 224 阅读