算法

(并查集) $O(n)$

若 $n$ 个点有 $x$ 个连通分量，那么至少要加 $x - 1$ 条边才能让所有点连通。

C++ 代码

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

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

    dsu d(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        d.merge(a, b);
    }

//  int cnt = 0;
//  rep(i, n) if (d.leader(i) == i) cnt++;
    int cnt = d.groups().size();
    int ans = cnt - 1; 
    cout << ans << '\n';

    return 0;
}