修路问题

1248762042

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

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

输入示例和题目不符，N在哪？M在哪？才明白原来是4个示例

jhq999

#include<stdio.h>
#include<stdlib.h>

void roadoutput(int (*road)[3],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[j][0]||i==road[j][1])
                        {
                                break;;
                        }
                }
                if (j==m)
                {
                        count++;
                }
        }
        for (i = 0; i < m; i++)//把互通的找出来算成一个孤立的城镇
        {
                if (!road[i][2])
                {
                        road[i][2]=1;
                        count++;

                        for (j = i+1; j < m; j++)
                        {
                                if (!road[j][2])
                                {
                                        if ((road[i][0]==road[j][0])||(road[i][1]==road[j][0])\
                                                ||(road[i][0]==road[j][1])||(road[i][1]==road[j][1]))
                                        {
                                                road[j][2]=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)[3]=(int(*)[3])malloc(m*3*sizeof(int));
                for (i = 0; i <m; i++)
                {
                        scanf("%d %d",&road[i][0],&road[i][1]);
                        road[i][2]=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

learner-ray

#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[100]; // 将还需要几条路存储在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];         // 现存m条路因此定义了一个exi[m]的数组，来存放。 
                
                for (i = 0; i < m; i++)                //输入城镇和道路信息； 
                {
                        scanf("%d%d", &(exi[i].t1), &(exi[i].t2));
                        if (exi[i].t1 > n || exi[i].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[i].t1 == exi[k].t1 && exi[i].t2 == exi[k].t2) || (exi[i].t1 = exi[k].t2 && exi[i].t2 == exi[k].t1))
                                {
                                        count++;
                                        break; //非常重要，防止重复计数。 
                                }
                        }
                }
                
                road[j++] = (n-1) - (m-count);         // n-1为需要的路径，m-count为现有的有效路径。 
        }
        
        printf("输出结果\n");
        
        for (i = 0; i < j; i++)
        {
                printf("%d\n", road[i]);
        }
        
        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
请按任意键继续. . .

1248762042

#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[size+1];
        U->root = new int[size+1];
        for (int e = 1; e <= size; e++)
        {
                U->parent[e] = 1;
                U->root[e] = 1;
        } 
        return U;
}

int UFfind(int e, UFset U)
{
        int i, j = e;
        while ( !U->root[j] )
        {
                j = U->parent[j];
        }
        while ( j != e )
        {
                i = U->parent[e];
                U->parent[e] = j;
                e = i;
        }
        return j;
}

int UFunion(int i, int j, UFset U)
{
        if (i == j) return i;
        if (U->parent[i] < U->parent[j])
        {
                U->parent[j] += U->parent[i];
                U->root[i] = 0;
                U->parent[i] = j;
                return j;
        }
        else {
                U->parent[i] += U->parent[j];
                U->root[j] = 0;
                U->parent[j] = 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

1248762042 发表于 2021-11-16 12:22

我自己写出来了