G7015 [GESP202509 七级] 连通图 题解

知识点：并查集、连通分量、图。

解题思路

用并查集合并每条边两端，统计最终连通分量数c，答案为c-1。代码从n-1开始，每次有效合并减1。

为什么正确

一条新边至多把分量数减少1，至少需c-1条；将各分量连成链即可达到。

易错点

重复边或本已连通的两点不能再减少答案；本实现使用路径压缩，未显式按秩合并。

复杂度

时间近似O((n+m)log n)保守界，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>p(n+1);
    iota(p.begin(),p.end(),0);
    function<int(int)>f=[&](int x) {
        return p[x]==x?x:p[x]=f(p[x]);
    }
    ;
    int ans=n-1;
    while(m--) {
        int u,v;
        cin>>u>>v;
        u=f(u);
        v=f(v);
        if(u!=v) {
            p[u]=v;
            ans--;
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。