修路问题
畅通工程某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出一个正整数和一个非负整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
输入示例
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
输出示例
1
0
2
998 本帖最后由 jhq999 于 2021-11-15 19:34 编辑
输入示例和题目不符，N在哪？M在哪？才明白原来是4个示例 本帖最后由 jhq999 于 2021-11-15 22:01 编辑
#include<stdio.h>
#include<stdlib.h>
void roadoutput(int (*road),int m,int n)
{
int i=0,j=0,count=0;
for (i = 1; i <= n; i++)//找出没通路的
{
for (j = 0; j < m; j++)
{
if (i==road||i==road)
{
break;;
}
}
if (j==m)
{
count++;
}
}
for (i = 0; i < m; i++)//把互通的找出来算成一个孤立的城镇
{
if (!road)
{
road=1;
count++;
for (j = i+1; j < m; j++)
{
if (!road)
{
if ((road==road)||(road==road)\
||(road==road)||(road==road))
{
road=1;
}
}
}
}
}
printf("%d\n",count-1);//孤立的城镇互通最少的路的条数是孤立的城镇数量-1
}
int main()
{
int i=0,j=0,n=0,m=0;
while (1)
{
scanf("%d",&n);
if (!n)
{
break;
}
scanf("%d",&m);
int (*road)=(int(*))malloc(m*3*sizeof(int));
for (i = 0; i <m; i++)
{
scanf("%d %d",&road,&road);
road=0;
fflush(stdin);
}
roadoutput(road,m,n);
free(road);
}
return 0;
}
10 4
1 2
3 4
5 6
9 10
5
10 6
1 2
1 3
2 3
4 5
8 9
9 10
4
4 2
1 3
4 3
1
3 3
1 2
1 3
2 3
0
5 2
1 2
3 5
2
999 0
998
0 #include<stdio.h>
void RoadNum(void);
int main(void)
{
RoadNum();
return 0;
}
void RoadNum(void) //该函数用来实现修路问题，整体思想为n个城镇至少需要n-1条有效路径。m是现存的路径，需要判断里面是否有无效路径，比如同时存在1 2 2 1。
{
int n, m; // n为城镇数量，m 为现存路径。
int count = 0; //用来统计m中的无效路径。
int i, k; //用来循环
int j= 0; //用来存储还需要几条路。
int road; // 将还需要几条路存储在road数组中。
printf("请输入城镇和道路信息：\n");
while (1)
{
count = 0; //辅助统计现有多少条路。
scanf("%d", &n);
if (n == 0) // 设置循环终止条件，输入0结束。
{
break;
}
scanf("%d", &m);
struct Exist // 每一条路是两个城镇来表示，因此定义了一个结构体来表示。
{
int t1;
int t2;
};
struct Exist exi; // 现存m条路因此定义了一个exi的数组，来存放。
for (i = 0; i < m; i++) //输入城镇和道路信息；
{
scanf("%d%d", &(exi.t1), &(exi.t2));
if (exi.t1 > n || exi.t2 > n) //假如5个城镇的话，用1，2，3，4，5来表示，输入的数字不能超过5，否则报错。
{
printf("输入错误\n");
return;
}
}
for (i = 0; i < m; i++) // 无效路径的判断。
{
for (k = i+1; k < m; k++)
{
if ((exi.t1 == exi.t1 && exi.t2 == exi.t2) || (exi.t1 = exi.t2 && exi.t2 == exi.t1))
{
count++;
break; //非常重要，防止重复计数。
}
}
}
road = (n-1) - (m-count); // n-1为需要的路径，m-count为现有的有效路径。
}
printf("输出结果\n");
for (i = 0; i < j; i++)
{
printf("%d\n", road);
}
return;
}
结果显示：
请输入城镇和道路信息：
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
输出结果
1
0
2
998
--------------------------------
Process exited after 11.71 seconds with return value 0
请按任意键继续. . . #include <iostream>
using namespace std;
typedef struct ufset *UFset;
typedef struct ufset
{
int *parent;
int *root;
}UFS;
UFset UFinit(int size)
{
UFset U = new ufset;
U->parent = new int;
U->root = new int;
for (int e = 1; e <= size; e++)
{
U->parent = 1;
U->root = 1;
}
return U;
}
int UFfind(int e, UFset U)
{
int i, j = e;
while ( !U->root )
{
j = U->parent;
}
while ( j != e )
{
i = U->parent;
U->parent = j;
e = i;
}
return j;
}
int UFunion(int i, int j, UFset U)
{
if (i == j) return i;
if (U->parent < U->parent)
{
U->parent += U->parent;
U->root = 0;
U->parent = j;
return j;
}
else {
U->parent += U->parent;
U->root = 0;
U->parent = i;
return i;
}
}
void UFfree(UFset U)
{
delete [] U->parent;
delete [] U->root;
delete U;
}
void uni(int x, int y, UFset uf)
{
int a = UFfind(x, uf),
b = UFfind(y, uf);
UFunion(a, b, uf);
}
int main()
{
int N, M, index1, index2, count;
UFset uf;
while (true)
{
count = 0;
cin >> N;
if ( N == 0 ) break;
cin >> M;
uf = UFinit(N);
for (int i = 0; i < M; i++)
{
cin >> index1 >> index2;
uni(index1, index2, uf);
}
for (int i = 1; i <= N; i++)
{
int j = UFfind(i, uf);
if ( i == j ) count++;
}
cout << count - 1 << endl;
UFfree(uf);
}
} 1248762042 发表于 2021-11-16 12:22
我自己写出来了
页:
[1]