https://codeforces.com/contest/1133/problem/F2
题解:先把与1无关的点合并,然后找与一相关必须连接的边,对于答案树想连必须的边,再连其他一相关边,最后连其他边
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum,u,v,d;
int a[N];
int pre[N];
int preans[N];
int vis[N];
bool broken[N];
char str;
vector<int>G[N];
struct Node{
int u,v;
bool operator <(const Node&S)const{
if(u==S.u)
return v<S.v;
return u<S.u;
}
}x;
vector <Node>ANS;
int find(int x){return (pre[x]==x)?x:pre[x]=find(pre[x]);}
int findans(int x){return (preans[x]==x)?x:preans[x]=findans(preans[x]);}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
if((int)G[1].size()<d){
cout<<"NO"<<endl;
return 0;
}
for(int i=1;i<=n;i++){
pre[i]=i;
preans[i]=i;
}
for(int i=2;i<=n;i++){
for(int j=0,k=G[i].size();j<k;j++){
u=i;
v=G[i][j];
if(v==1)
continue;
int tx=find(u);
int ty=find(v);
if(tx!=ty){
pre[tx]=ty;
}
}
}
for(int i=0,j=G[1].size();i<j;i++){
u=1;
v=G[1][i];
int tx=find(u);
int ty=find(v);
if(tx!=ty){
pre[tx]=ty;
//cout<<u<<" "<<v<<endl;
x.u=u;
x.v=v;
int ta=findans(u);
int tb=findans(v);
preans[ta]=tb;
ANS.push_back(x);
if(++cnt>=d)
break;
}
}
for(int i=0,j=G[1].size();i<j;i++){
u=1;
v=G[1][i];
int ta=findans(u);
int tb=findans(v);
if(cnt>=d)
break;
if(ta!=tb){
//cout<<u<<" "<<v<<endl;
cnt++;
x.u=u;
x.v=v;
preans[ta]=tb;
ANS.push_back(x);
}
}
for(int i=2;i<=n;i++){
for(int j=0,k=G[i].size();j<k;j++){
u=i;
v=G[i][j];
if(v==1)
continue;
int ta=findans(u);
int tb=findans(v);
if(ta!=tb){
//cout<<u<<" "<<v<<endl;
x.u=u;
x.v=v;
preans[ta]=tb;
ANS.push_back(x);
}
}
}
flag=0;
for(int i=1;i<=n;i++){
if(pre[i]==i){
flag++;
}
}
if(flag>1){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
sort(ANS.begin(),ANS.end());
for(int i=0,j=ANS.size();i<j;i++){
x=ANS[i];
cout<<x.u<<" "<<x.v<<endl;
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N=2e5+10;
int par[MAX_N]; //父亲
int ranks[MAX_N]; //树的高度
struct Edge{int u,v;};
Edge edges[MAX_N];
int cnt[MAX_N]={0,};
int n,m,k;
int ans[MAX_N],q=0;
void init(){
for(int i=1;i<=n;i++){
par[i]=i;
ranks[i]=0;
}
}
int findit(int x){
if(par[x]==x)
return x;
else
return par[x]=findit(par[x]);
}
void unite(int x, int y){
x=findit(x);
y=findit(y);
if(x==y) return;
if(ranks[x]<ranks[y])
par[x]=y;
else par[y]=x;
if(ranks[x]==ranks[y])
ranks[x]++;
}
bool same(int x, int y){
return findit(x)==findit(y);
}
int main(void){
scanf("%d %d %d",&n,&m,&k);
init();
for(int i=0;i<m;++i)
{
scanf("%d %d",&edges[i].u,&edges[i].v);
cnt[edges[i].u]++;
cnt[edges[i].v]++;
}
if(cnt[1]<k){
printf("NO\n");
return 0;
}
//先把剩下的点连起来
for(int i=0;i<m;++i)
if(edges[i].u!=1&&edges[i].v!=1)
if(!same(edges[i].u,edges[i].v))
unite(edges[i].u,edges[i].v);
//得到顶点1必须选用的边
for(int i=0;i<m;++i){
if(edges[i].u==1||edges[i].v==1){
if(!same(edges[i].u,edges[i].v)){
unite(edges[i].u,edges[i].v);
ans[q++]=i;
}
}
}
if(q>k){
printf("NO\n");
return 0;
}
//重新初始化
init();
printf("YES\n");
for(int i=0;i<q;++i){
unite(edges[ans[i]].u,edges[ans[i]].v);
printf("%d %d\n",edges[ans[i]].u,edges[ans[i]].v);
}
for(int i=0;i<m&&q<k;++i){
if(edges[i].u==1||edges[i].v==1){
if(!same(edges[i].u,edges[i].v)){
unite(edges[i].u,edges[i].v);
printf("%d %d\n",edges[i].u,edges[i].v);
q++;
}
}
}
//再连其他点
for(int i=0;i<m;++i){
if(edges[i].u!=1&&edges[i].v!=1){
if(!same(edges[i].u,edges[i].v)){
unite(edges[i].u,edges[i].v);
printf("%d %d\n",edges[i].u,edges[i].v);
}
}
}
}