【正经题解】村村通

使用深度优先搜索（ $DFS$ ）遍历城镇，标记连通的城镇。
对每个未被标记的城镇进行 $DFS$ ，每次 $DFS$ 完成表示找到一个新的连通分量。
统计连通分量的个数，并输出连通分量个数减 $1$ ，即最少需要建设的道路数目。因为每个连通分量之间只需要一条道路。

#include<bits/stdc++.h>
using namespace std;

vector<int> vis(1005);
int cnt;
vector<int> v[1005];

// 深度优先搜索，标记连通的城镇
void dfs(int x) {
    vis[x] = 1;
    for (auto i : v[x]) {
        if (!vis[i]) dfs(i);
    }
}

// 计算最少需要建设的道路数目
int calculateRoads(int n, int m) {
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt++;
            dfs(i);
        }
    }
    return cnt - 1;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 输入城镇直接相连的城镇
    while (m--) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    // 计算最少需要建设的道路数目并输出结果
    int result = calculateRoads(n, m);
    cout << result;

    return 0;
}