P10530 [XJTUPC2024] 生命游戏

Rigel · 2024-09-03 21:01:31 · 题解

题意

给定一棵 n 个点、n-1 条边的树。每轮找到所有度数为 k 的点并删去这些点与其连接的所有边。求最后的连通块个数。

思路

按题意模拟即可。

采用邻接链表存图，建双向边，并维护每个点的度数。

考虑队列。首先将所有度数为 k 的点入队并标记。

每一轮开始，遍历所有与队首（本轮结束后将删去的点）相连的点。若一个点不在队列中（无标记），则将其度数减 1。若此时该点度数为 k，则将其编号存入 t 数组。因为此轮结束后，此点的度数可能仍为 k，在下一轮可能被删去。遍历完后，队列头指针后移，继续遍历下一个即将删去的点所连接的点，重复上述操作，直至队空。

每一轮结束后，判断 t 数组中每个点的度数是否依旧为 k。若是，将其入队并标记。最后清空 t 数组。

重复操作，直至队列为空，即没有度数为 k 的点可以删除。统计连通块个数即可出答案。

代码

#include<bits/stdc++.h>
#define int long long
#define maxn 1000010
using namespace std;
int n,k,tot,deg[maxn],lnk[maxn],q[maxn],t[maxn],vis[maxn],f[maxn],ans;
struct edge{
    int to,nxt;
}e[maxn*2];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}
void add_edge(int x,int y){
    e[++tot]=(edge){y,lnk[x]};
    lnk[x]=tot;
}
void dfs(int x){
    f[x]=1;
    for(int i=lnk[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(f[v]||vis[v])continue;
        f[v]=1;
        dfs(v);
    }
}
void bfs(){
    int hed=0,til=0;
    for(int i=1;i<=n;i++)if(deg[i]==k)q[++til]=i,vis[i]=1;
    while(hed!=til){
        int tot1=0;
        while(hed!=til){
            hed++;
            int u=q[hed];
            deg[u]=0,vis[u]=1;
            for(int i=lnk[u];i;i=e[i].nxt){
                int v=e[i].to;
                if(vis[v]==1)continue;
                deg[v]--;
                if(deg[v]==k)t[++tot1]=v;
            }
        }
        for(int i=1;i<=tot1;i++)if(deg[t[i]]==k)q[++til]=t[i],vis[t[i]]=1;
    }
}
signed main(){
    n=read(),k=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add_edge(u,v),add_edge(v,u);
        deg[u]++,deg[v]++;
    }
    bfs();
    for(int i=1;i<=n;i++)if(!vis[i]&&!f[i])ans++,dfs(i);
    printf("%lld\n",ans);
    return 0;
}