描述：
国家建设高铁网络，网络由一些连接城市的高铁线路构成。现有高铁建设情况可列为一张统计表，表中列出了每一条高铁线路直接连接的两个城市。国家的建设目标是全国每两个城市之间都可以实现高铁交通（但不一定有直接的高铁线路相连，只要能间接通过高铁线路可达即可）。问最少还要建设多少条高铁线路？
输入说明：
测试用例的第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求解。
领接矩阵存无向图边要存两遍！！！！！！
该问题是dfs的典型应用，dfs函数讲究的就是两个点
1.注意边界，避免越界
2.走出这一步前，需要小心小心再小心，看看这条路能不能走，有没有越界，而走上去了之后，就要大胆一点，这个地方是满足我要求的
#include<iostream> using namespace std; #define MAXN 1500 int grid[MAXN][MAXN]; int vis[MAXN]; int n,m;//n nodes m edge; int ans=0; void dfs(int i) { vis[i]=1; for(int k=1;k<=n;k++) { if(grid[i][k]==1&&vis[k]==0) dfs(k); } return; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int j,k; cin>>j>>k; grid[j][k]=1; grid[k][j]=1; } for(int i=1;i<=n;i++) { if(vis[i]==0) { ans++; dfs(i); } } cout<<ans-1; return 0; }
