自动搬运

查看原文

来自洛谷，原作者为

	Rigel 苍山负雪，明烛天南。|| 高二现役 OIer。

搬运于2025-08-24 22:58:54，当前版本为作者最后更新于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;
}