A558.村村通-题解

第一眼：图；第二眼：连通块；第三眼：图+连通块(bushi）

经过画图推理，我们发现：添加道路数量=连通块数量-1

然后就AC了

AC代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>v[1001];
int vis[1001];
//标记连通块
void dfs(int i){
    vis[i]=1;
    for(int j=0;j<v[i].size();j++)
        if(!vis[v[i][j]]) dfs(v[i][j]);
}
int main(){
    int n,m,x,y,ans=0;
    //输入
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> x >> y;
        //无向图
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        dfs(i);
        ans++;  //统计连通块数量
    }
    cout << ans-1; //添加道路数量=连通块数量-1
    return 0;
}

给个免费的点赞呗~~