C语言实现畅通工程：最小生成树问题 (Kruskal算法)

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

输入： 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。

注意:两个城市之间可以有多条道路相通,也就是说

这种输入也是合法的

当N为0时，输入结束，该用例不被处理。

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

样例输入：

样例输出：

分析：

这道题是典型的最小生成树问题，可以使用Kruskal或Prim算法来解决。本题使用Kruskal算法。

Kruskal算法的基本思想是，将图中的所有边按照权值大小从小到大排序，然后依次选择权值最小的边，若该边的两个端点不在同一个集合中，则将这两个端点所在的集合合并为一个集合。

具体实现时，可以使用并查集来维护集合的关系，每次选择一条合法的边，判断两个端点是否在同一个集合中，若不在，则将两个集合并成一个，同时将边的长度加入到答案中。

代码：

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

using namespace std;

#define MAXN 1000

struct Edge {
    int u, v, w;
} edge[MAXN * MAXN];

int n, m;
int fa[MAXN];

bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void Union(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
    }
}

int Kruskal() {
    int cnt = 0, ans = 0;
    sort(edge, edge + m, cmp);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        if (find(edge[i].u) != find(edge[i].v)) {
            Union(edge[i].u, edge[i].v);
            ans += edge[i].w;
            cnt++;
            if (cnt == n - 1) {
                break;
            }
        }
    }
    return ans;
}

int main() {
    while (scanf("%d %d", &n, &m) != EOF && n) {
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &edge[i].u, &edge[i].v);
            edge[i].w = 1; // 边的权值默认为1
        }
        printf("%d\n", n - 1 - Kruskal()); // 最少还需要建设的道路数目
    }
    return 0;
}

代码解释：

首先定义结构体Edge，用来存储边的信息，包括边的起点u，终点v和权值w。
数组fa用来存储并查集的父节点信息，初始化时每个节点的父节点为自己。
函数cmp用来比较边的权值，从小到大排序。
函数find用来查找一个节点所在集合的根节点，使用路径压缩优化。
函数Union用来合并两个集合。
函数Kruskal实现Kruskal算法，首先排序所有边，然后依次遍历，如果两个端点不在同一个集合中，则合并这两个集合，并将边的权值加入到答案中。
主函数中，首先读取输入数据，然后调用Kruskal函数计算最小生成树的权值，最后输出结果。

注意：

本代码中边的权值默认为1，因为题意没有给出边的权值信息，只需要计算需要建设的道路数量。
由于输入数据中可能存在重复边，需要在Kruskal函数中判断两个端点是否在同一个集合中，以避免重复计算。
代码中使用了#define MAXN 1000来定义数组的大小，可以根据实际情况进行调整。

总结：

本篇文章介绍了使用C语言解决“畅通工程”问题的方法，并使用Kruskal算法进行实现。代码简洁易懂，并包含详细的解释和注释，方便读者理解和学习。

扩展：

除了Kruskal算法，还可以使用Prim算法来解决最小生成树问题。Prim算法的基本思想是从一个节点开始，每次选择离当前集合最近的节点加入到集合中，直到所有节点都被加入到集合中。Prim算法的实现比Kruskal算法略微复杂一些，但是时间复杂度更低。

希望本篇文章能够帮助读者更好地理解最小生成树问题以及Kruskal算法。