题解 | #畅通工程#

#include<iostream>
#include<map>
#include<vector>
using namespace std;
map<int,int> visited;
void dfs(map<int,vector<int> > mp,int start){
    if(visited[start] == 1)
        return;
    visited[start] = 1;
    for(auto it : mp[start]){
        if(!visited[it]){
            dfs(mp,it);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,s,e,cnt = -1;
    map<int,vector<int> > mp;
    while(cin >> n >> m){
        for(int i = 0;i < m;++i){
            cin >> s >> e;
            mp[s].push_back(e);
            mp[e].push_back(s);
        }
        //判断是否相连
        for(int i = 1;i <= n;++i){
            if(!visited[i]){
                dfs(mp,i);
                cnt++;
            }
        }
        cout << cnt << endl;
        mp.clear();
        visited.clear();
        cnt = -1;
    }
}