我要招人

去企业版

首页 > 试题广场 >

畅通工程

[编程题]畅通工程

热度指数：13159 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
    注意:两个城市之间可以有多条道路相通,也就是说
    3 3
    1 2
    1 2
    2 1
    这种输入也是合法的
    当N为0时，输入结束，该用例不被处理。

输出描述:

    对每个测试用例，在1行里输出最少还需要建设的道路数目。

示例1

输入

输出

算法知识视频讲解

wonderab

发表于 2020-06-08 11:20:31

//将每个元素看为一个集合，然后通过并查集合并集合，然后再将余下的集合连接起来即可 #include<iostream> #include<vector> using namespace std; int main(){ int n,m; while(cin& 展开全文

慢慢且漫漫~

发表于 2022-05-05 10:14:41

一、解题流程： 1. 循环输入城镇和道路数 2. 初始化：初始化2个数组 father，height（Initial函数）将所有城镇看为一个独立的个体，此时爸爸是自己，高度为0 3. 输入相连的城镇：（1）查找城镇所在集合即“查找集合根节点”（Find函数）（2）不在同一集合进行合并（展开全文

philos

发表于 2021-03-07 14:13:13

思路并查集求出有多少个连通分支即可，这几道并查集的题目都可以用模板解的，下面这个模板没有很完整，所以用的时候够用就行，并且其实不新建一个类也行，我只是想告诉大家整个并查集的逻辑。 #include<iostream> #include<vector> #include< 展开全文

yyer

发表于 2023-03-07 20:46:49

#include <iostream> using namespace std; const int N=1002; int n,m,a,b; int cont; int G[N][N]; bool visited[N]={false}; void Initial(){ cont 展开全文

T790T

发表于 2024-08-03 10:01:52

#include <bits/stdc++.h> using namespace std; int fa[1005], he[1005]; int find(int n) { if (n == fa[n]) return n; fa[n] = find(fa[n]); 展开全文

牛客440904392号

发表于 2024-09-30 20:31:55

import java.util.Scanner; public class Main { private static int[] parents; public static void main(String[] args) { Scanner sc = new 展开全文

着力登峰

发表于 2023-08-23 20:38:31

#include<iostream> using namespace std; // 畅通工程 const int MAX = 1000; int father[MAX]; int height[MAX]; void Initial(int n) { for (int i = 0 展开全文

土尔逊Torson

发表于 2023-06-16 21:40:51

//土尔逊Torson 编写于2023/06/16 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> using namespace std; const int MAXN = 10 展开全文

Huster水仙

发表于 2023-02-02 11:52:14

求连通分量个数——并查集 #include<iostream> using namespace std; const int maxn=1010; int city[maxn]; int height[maxn]; void Initial(int n){ for(int i 展开全文

Shawn698

发表于 2024-03-20 20:38:37

#include "bits/stdc++.h" using namespace std; int father[5000]; int height[5000]; struct Edge { int begin; int end; int cost; 展开全文

问题信息

图高级结构并查集

难度：

62条回答 153收藏 10032浏览

通过挑战的用户

查看代码

快乐冒险家

2023-03-12 16:22:53
就是我的

2023-03-10 17:46:29
刷了100道题...

2023-03-09 09:52:57
_cherry

2023-03-08 11:18:50
你的生活我的梦a

2023-02-28 20:09:33

畅通工程

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题