高铁网络
描述：
国家建设高铁网络，网络由一些连接城市的高铁线路构成。现有高铁建设情况可列为一张统计表，表中列出了每一条高铁线路直接连接的两个城市。国家的建设目标是全国每两个城市之间都可以实现高铁交通（但不一定有直接的高铁线路相连，只要能间接通过高铁线路可达即可）。问最少还要建设多少条高铁线路？
输入说明：
测试用例的第1行给出两个正整数，分别是城市数目N(<1000)和现有高铁线路数目M。随后的M行对应M条高铁线路，每行给出一对正整数，分别是该条高铁线路直接连接的两个城市的编号。为简单起见，城市从1到N编号。
输出说明：
在一行上输出最少还需要建设多少条高铁线路。
输入样例：
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9
输出样例：
2
实现提示：
该问题实质为求连通分量的个数减一，可用深度优先或广度优先搜索求解，也可用MFSet求解。
#include<stdio.h>
#include<stdlib.h>
int vset[100];
int findset(int x)
{
while (vset[x] != 0)
x = vset[x];
return x;
}
int main()
{
int m, n, i, a, b, va, vb, count;
scanf("%d", &n);
for (i = 0; i < n; i++)
vset[i] = 0;
scanf("%d", &m);
for (i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
va = findset(a);
vb = findset(b);
if (va != vb)
vset[va] = vb;
}
count = 0;
for (i = 0; i < n; i++)
{
if (vset[i] == 0)
count++;
}
printf("%d", count-1);
return 0;
}
原文：https://www.cnblogs.com/KIROsola/p/11909403.html