【Codeforces Round #544 (Div. 3) F2. Spanning Tree with One Fixed Degree】DFS

F2. Spanning Tree with One Fixed Degree

题意

给你$n$个点$m$条边的无向联通图，找出一棵生成树，使$1$这个点的度$=d$。

$1\le n,m\le 10^5$
做法

首先我们把$1$这个点先拿出来，如果$1$的度最初就小于$d$，答案一定不存在，否则对除$1$这个点之外剩下的图求连通分量，并记录每个连通分量之内有哪些点与$1$相连，之后为保证联通，每个连通分量一定至少和$1$连一条边，之后如果此时$1$的度已经超过$d$，则答案不存在，否则将多余的度与那些之前没连过而且与$1$有边的点相连即可。

代码

#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;
}