代码求 Hack 或思路证伪(悬2关)
查看原帖
代码求 Hack 或思路证伪(悬2关)
373198
WhileTrueRP楼主2024/4/6 15:16

思路: 所有的度为 11 的点所连的点一定是中心,中心所连接的点一定是叶子。

每次找一个度数为 11 的点,相连点的度数即为这个菊花图的大小。然后删掉这个菊花图,重复以上操作。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int> e[N];
priority_queue<int> ans;
queue<int> q; 
bool vis[N];
int du[N];
void add(int u,int v){
	e[u].push_back(v);
	e[v].push_back(u); 
	du[u] ++;
	du[v] ++;
}
void solve(){
	while(!q.empty()){
		int s = q.front();
		q.pop();
		if(vis[s]){
			continue;
		}
		int u = e[s][0];
		ans.push(-e[u].size());
		vis[u] = true;
		for(int i=0;i<e[u].size();i++){
			int v = e[u][i];
			if(vis[v]){
				continue;
			}
			vis[v] = true;
			for(int j=0;j<e[v].size();j++){
				du[e[v][j]] --;
				if(du[e[v][j]] == 1 && !vis[e[v][j]]){
					q.push(e[v][j]);
				}
			}
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		if(du[i] == 1){
			q.push(i);
		}
	}
	solve();
	while(!ans.empty()){
		printf("%d ",-ans.top());
		ans.pop();
	}
}
2024/4/6 15:16
加载中...