本题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232
结题思路：因为题目是汉语的，那我就不解释题意了，要求的是最少建设的道路，我们可以用并查集来做这道题，因为并查集上的数字和下标都是相连的。题目只需要求没有相连的（i == father[i]）即可。
注意细节：本题说是从1到N开始计数（虽然测试答案是对的，就是过不了）、输入的时候注意最后只是输入一个0就结束了，所以M和N要分开输，即输入N为0的时候。
我的代码：（因为是模板题，建议码友自己写一遍，代码仅供参考）：
#include <iostream>
#define maxn 10000
using namespace std;
int par[maxn]; void init (int n) {
for (int i = ; i <= n; ++i) //从1到N编号
par[i] = i;
} int find(int x) { //查找
while(par[x] != x)
x = par[x];
return x;
} void unite (int x, int y) { //合并函数
int fx = find (x), fy = find (y);
if (fx != fy)
par[fx] = fy;
} int main () {
int m, n;
int a, b;
while (cin >> m && m ) {//注意当输入一个0 的时候就停止
cin >> n;
init (m);
for (int i = ; i <= n; ++i) {
cin >> a >> b;
unite (a, b);
}
int t = ;
for (int i = ; i <= m; ++i) { //求独立的点
if (par[i] == i)
t ++;
}
cout << t - << endl;
}
return ;
}
欢迎码友评论，一起成长。