算法

(并查集) $O(n)$

本题实质上是求有多少个连通分量，而本题的答案就是连通分量个数$-1$。所以只需要统计有多少个树根就行了。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;

int p[N];

int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}

void Union(int x, int y) {
    p[find(x)] = find(y);
}

int main() {
    int n, m;

    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) p[i] = i;

        for (int i = 1, x, y; i <= m; ++i) {
            cin >> x >> y;
            Union(x, y);
        }

        int cnt = -1;
        for (int i = 1; i <= n; ++i) {
            if (p[i] == i) cnt++;
        }

        cout << cnt << '\n';
    }

    return 0;
}