F2. Spanning Tree with One Fixed Degree
题意
给你nnn个点mmm条边的无向联通图,找出一棵生成树,使111这个点的度=d=d=d。
1≤n,m≤1051 \leq n,m \leq 10^51≤n,m≤105
做法
首先我们把111这个点先拿出来,如果111的度最初就小于ddd,答案一定不存在,否则对除111这个点之外剩下的图求连通分量,并记录每个连通分量之内有哪些点与111相连,之后为保证联通,每个连通分量一定至少和111连一条边,之后如果此时111的度已经超过ddd,则答案不存在,否则将多余的度与那些之前没连过而且与111有边的点相连即可。
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 2e5+5;
#define Se second
#define Fi first
#define pb push_back
vector<int>G[maxn];
vector<int>dsu[maxn];
vector<int>one[maxn];
vector<pii> ans;
int n,m,d,in[maxn];
int vis[maxn];
int tot;
void dfs(int x)
{
dsu[tot].pb(x);vis[x]=1;for(int i=0;i<G[x].size();i++){
int to=G[x][i];if(vis[to]) continue;if(to==1){
one[tot].pb(x);continue;}dfs(to);}
}
int main()
{
int u,v;scanf("%d%d%d",&n,&m,&d);for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);in[u]++;in[v]++;G[u].pb(v);G[v].pb(u);}if(in[1]<d) return 0*puts("NO");for(int i=2;i<=n;i++){
if(!vis[i]){
++tot;dfs(i);}}if(tot>d) return 0*puts("NO");memset(vis,0,sizeof(vis));queue<int> q;vis[1]=1;for(int i=1;i<=tot;i++){
int b=one[i].back();ans.pb(pii(1,b));vis[b]=1;q.push(b);one[i].pop_back();d--;}for(int i=1;i<=tot;i++){
while(d>0&&one[i].size()>0){
int b=one[i].back();ans.pb(pii(1,b));vis[b]=1;q.push(b);one[i].pop_back();d--;}}while(!q.empty()){
int tp=q.front();q.pop();for(int i=0;i<G[tp].size();i++){
int to=G[tp][i];if(vis[to]) continue;ans.pb(pii(tp,to));vis[to]=1;q.push(to);}}puts("YES");for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].Fi,ans[i].Se);return 0;
}