题目描述
有n个城市，m条双向路的图，问你最少添加几条路使得任意两个城市可以两两到达？
样例
样例输入
3 1
1 2
样例输出：
1
题目解析
这是个双向路的图，我们可以把它当成一个非连通图。在各个点之间有连线，要求我们算出如何能将整个图的各个部分连接起来。那么，我们只要算出这个非连通图由几个区域（部分）组成。然后减1，也就是将他们连接起来的边的个数，那么此时，任意一个城市就能到其他任意的城市了。
代码实现
#include<bits/stdc++.h>
using namespace std;
int a[100005];
vector<int> b[100005];
void dfs(int u){
a[u]=1;
for(int v:b[u]){
if(!a[v]){
dfs(v);
}
}
//return ;
}
int find(int n){
int c=0;
for(int i=1;i<=n;i++){
if(!a[i]){
c++;
dfs(i);
}
}
return c;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
b[x].push_back(y);
b[y].push_back(x);
}
int c=find(n);
cout<<c-1<<endl;
return 0;
}
说明
这是我初一刚学算法那会写的代码，年久失修，不对的请指正。