自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:25:24，当前版本为作者最后更新于2021-11-04 17:02:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标题倒装句好评

首先把所有点的度数减一，那么给定度数序列，能构造出合法的树，当且仅当 $\sum d_i=n-2$。下面的构造证明了这一点。

• 方法：把所有点按度数从小到大排序，对每个点 $x$，找到其后面第一个度数非零（注意度数已经减一）的点 $y$，连接 $(x,y)$，把 $y$ 的度数减一。

那么原问题就转化为：

• 给定一些度数，请你选出最多的度数，满足和不超过 $n-2$。（因为如果还没达到 $n-2$ 可以再用剩下的一个点补齐）

排序后从小到大选即可。注意输出格式比较毒瘤。

#include <bits/stdc++.h>
using namespace std;
int n,m,d[10005],pl[10005];
int main(){
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,d[x]++,d[y]++;
	for(int i=0;i<n;i++)pl[i]=i,d[i]--;
	sort(pl,pl+n,[](int x,int y){return d[x]<d[y];});
	int s=0,ans=0;
	for(int i=0;i<n;i++){
		if(s+d[pl[i]]>n-2)break;
		s+=d[pl[i]],ans++;
	}
	cout<<n-ans<<'\n'<<n<<' '<<n-1<<'\n';
	for(int i=ans;i<n;i++){
		if(s==n-2)d[pl[i]]=0;
		else d[pl[i]]=1,s++;
	}
	sort(pl,pl+n,[](int x,int y){return d[x]<d[y];});
	for(int i=0,j=0;i+2<n;i++){
		while(!d[pl[j]])j++;
		d[pl[j]]--,cout<<pl[i]<<' '<<pl[j]<<'\n';
	}
	cout<<pl[n-2]<<' '<<pl[n-1]<<'\n';
}