题解：P14077 [GESP202509 七级] 连通图

· · 题解

思路

算是一道简单的并查集模板题。

题解

因为要使得所有的点之间联通，相当于把 n 个点划分为若干个不互相联通的块变得联通，而块的数量 - 1 = 需要加的边数量。

具体如何划分块，详见 并查集模板

具体详见代码注释

代码

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

#define endl '\n'
#define int long long
#define pii pair <int, int>
#define lc(i) (i << 1)
#define rc(i) (i << 1 | 1)
#define MAXN 100005
#define MAXM 1000005
int mod = 100000007;

int n, m;
int root[MAXN];//root[i]: i 点所在块的根节点

int search(int node) {
    if (root[node] == node)
        return  node;
    return root[node] = search(root[node]);//优化
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)//初始化，每一个点为一块
        root[i] = i;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        root[search(u)] = root[search(v)];//合并
    }
    int div = 0;//块数量
    for (int i = 1; i <= n; ++i) {
        if (search(i) == i) 
            ++div;
    }
    cout << div - 1 << endl;
    return 0;
}