Atcoder abl c

传送门

题目描述

有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;
}

说明

这是我初一刚学算法那会写的代码，年久失修，不对的请指正。