题解

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 5;
int parent[MAXN];

// 并查集查找（路径压缩）
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    // 处理每条边，合并连通块
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int fu = find(u);
        int fv = find(v);
        if (fu != fv) {
            parent[fu] = fv;
        }
    }

    // 统计连通块数量
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (find(i) == i) { // 根节点
            cnt++;
        }
    }

    // 最少需要添加的边数：连通块数 - 1
    cout << cnt - 1 << endl;

    return 0;
}