题解 P1536 【村村通】

· · 题解

并查集+桶排序

显然，城镇之间构成了一个又一个的集合

而对于集合的每一个元素（城镇）又没有特殊限定

那我们直接用并查集解决

每建一条公路，就是把两城镇所在的集合合并

显然，对于n个不同的集合，想要把它们连起来

至少需要连n-1条线

那我们求出一共有多少个集合

把集合数减去1，输出，搞定！

如何求集合的数量呢？

每个集合都有一个“祖宗”

又知道“祖宗”的序号不会超过1000

那好办，桶排序啊！

每遇到一个城镇，就把它的“祖宗”对应的下标变为1

我们可以通过路径压缩使同一个集合的城镇拥有同一个祖宗

那最后遍历桶，看看有多少被标为1的元素不就行了

注意有多组数据哦

代码来了~

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1001;//定义常量maxn作为数组大小
int a[maxn];//并查集a
bool ok[maxn];//桶
int cz(int x){//并查集查找函数
    if(a[x]==x) return x;
    else return a[x]=cz(a[x]);//路径压缩
}
void hb(int x,int y){//合并函数
    int x1=cz(x),y1=cz(y);
    a[x1]=a[y1];
}
int main(){
    int n,m,x,y,ans;
    while(1){
        scanf("%d",&n);//先读一个数据
        if(n==0) break;//是0，停止读入
        scanf("%d",&m);//不是0，继续
        ans=0;//集合数量
        for(int i=1;i<=n;++i){
            a[i]=i;//并查集初始化
        }
        for(int i=1;i<=m;++i){
            scanf("%d%d",&x,&y);//把x,y两个城镇连起来
            hb(x,y);//就是合并x,y所在的集合
        }
        for(int i=1;i<=n;++i){
            ok[cz(i)]=1;//入桶
        }
        for(int i=1;i<=n;++i){
            if(ok[i]) ans++;//被标记过，代表着一个集合
        }
        printf("%d\n",ans-1);//输出答案
        memset(ok,0,sizeof(ok));//清空桶
    }
    return 0;
}

你AC了没？AC了就点个赞呗