UCV2013H - Slick题解

zjinze · 2023-12-17 18:06:13 · 题解

思路：

用并查集来维护连通块，可以快速查询每个连通块的大小。这时我们只需要向一个是石油的点的四周拓展，看那个点是不是石油。如果是，则加入到连通块中。最后，我们可以将所有联通块，按面积从小到大排序，再按题目格式输出即可。

code:

#include <bits/stdc++.h>
using namespace std;
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return ;
}
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t,n,m,a[510][510],Father[510*510],siz[510*510],tot=0,cnt=0;
int calc(int x,int y){
    return (x-1)*m+y;
}
unordered_map<int,bool>ma; 
struct node{
    int area;
}ans[510*510];
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            Father[calc(i,j)]=calc(i,j);
            siz[calc(i,j)]=1;
        }
    }
}
int find(int x){
    if(Father[x]!=x){
        Father[x]=find(Father[x]);
    }
    return Father[x];
}
void merge(int x,int y){
    if(x!=y){
        Father[y]=x;
        siz[x]+=siz[y];
    }
    return ;
}
bool cmp(const node &x,const node &y){
    return x.area<y.area;
}
int main(){
    while(1){
        n=read();
        m=read();
        if(n==0 && m==0)break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=read();
            }
        }
        init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]==1 && a[i+1][j]==1 && i+1<=n){
                    merge(find(calc(i,j)),find(calc(i+1,j)));
                }
                if(a[i][j]==1 && a[i-1][j]==1 && i-1>=1){
                    merge(find(calc(i,j)),find(calc(i-1,j)));
                }
                if(a[i][j]==1 && a[i][j+1]==1 && j+1<=m){
                    merge(find(calc(i,j)),find(calc(i,j+1)));
                }
                if(a[i][j]==1 && a[i][j-1]==1 && j-1>=1){
                    merge(find(calc(i,j)),find(calc(i,j-1)));
                }
            }
        }
        ma.clear();
        cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(ma[find(calc(i,j))]==false && a[i][j]==1){
                    ma[find(calc(i,j))]=true;
                    ans[++cnt].area=siz[find(calc(i,j))];
                }
            }
        }
        sort(ans+1,ans+cnt+1,cmp);
        int la=-1;
        tot=0;
        ma.clear();
        cout<<cnt<<endl;
        for(int i=1;i<=cnt;i++){
            if(!ma[ans[i].area]){
                if(tot!=0){
                    write(tot);
                    puts("");
                }
                write(ans[i].area);
                printf(" ");
                tot=1; 
                ma[ans[i].area]=true;
            }
            else{
                ++tot;
            }
        }
        if(tot){
            write(tot);
            puts("");
        }
    }
    return 0;
}