P1536 村村通——题解

解题思路

用并查集合并每条道路的两个端点。处理完后统计不同集合的数量 $k$。每新建一条道路最多把两个连通块合并为一个，因此至少需要 $k-1$ 条；把这些连通块依次连接也确实只需要 $k-1$ 条。

复杂度分析

每组时间复杂度近似为 $O((n+m)\alphalpha(n))$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int fa[1005];
int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m;
    while(cin>>n && n){
        cin>>m;
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=0;i<m;i++){
            int a,b; cin>>a>>b;
            a=findf(a); b=findf(b);
            if(a!=b) fa[a]=b;
        }
        int cnt=0;
        for(int i=1;i<=n;i++) if(findf(i)==i) cnt++;
        cout<<cnt-1<<'\n';
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int fa[1005]; int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; while(cin>>n && n){ cin>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a=findf(a); b=findf(b); if(a!=b) fa[a]=b; } int cnt=0; for(int i=1;i<=n;i++) if(findf(i)==i) cnt++; cout<<cnt-1<<'\n'; } return 0; }