首页 > 代码库 > 洛谷 P1536 村村通 题解

洛谷 P1536 村村通 题解

2024-10-17 14:23:40   213人阅读

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。

题目链接：https://www.luogu.org/problem/show?pid=1536

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入输出格式

输入格式：

每个输入文件包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目N（N<1000）和道路数目M；随后的M行对应M条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从1到N编号。

注意：两个城市间可以有多条道路相通。例如：

3 31 21 22 1这组数据也是合法的。当N为0时，输入结束。

输出格式：

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

输入输出样例

输入样例#1：
4 21 34 33 31 21 32 35 21 23 5999 00
输出样例#1：
102998


分析：
感觉这题比最小生成树的模板还要简单，只要判断是不是生成了树就可以了。排序之类的操作都不需要，
只要把边连一连，输出比n-1少的边数，就是需要建的道路。实际上是一个并查集。


AC代码：
#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int MAXN = 1010;const int MAXM = 20000;int fa[MAXN],m,n;inline void read(int &x){    char ch = getchar();char c;x = 0;    while(ch > ‘9‘ || ch < ‘0‘)    c = ch,ch = getchar();    while(ch <= ‘9‘ && ch >= ‘0‘)    x = x*10+ch-‘0‘,ch = getchar();    if(c == ‘-‘)    x = ~x+1;}struct edge{    int f,t,v;}e[MAXM];int find(int x){    if(fa[x] == x)        return x;    return fa[x] = find(fa[x]);}bool Union(int x,int y){    x = find(x),y = find(y);    if(x != y)    {        fa[x] = y;        return 1;    }    return 0;}int main(){    while(scanf("%d%d",&n,&m) == 2)    {        if(n == 0)    break;        for(int i = 1;i <= n;i ++)            fa[i] = i;        for(int i = 1;i <= m;i ++)            read(e[i].f),read(e[i].t);//不需要读入边权        int cnt = n;        for(int i = 1;i <= m && cnt > 1;i ++)        {            if(Union(e[i].f,e[i].t))                cnt --;        }        printf("%d\n",cnt - 1);//需要建的道路数    }    return 0;}
 
洛谷 P1536 村村通 题解






























        

            
                
                  
                
                

                    联系

                    我们