P10179 题解

· · 题解

题目解析

给定几个点对，要求构造一棵树，使得所有给定点对距离皆为 2.

首先我们发现，如果有一个点没被任何点对包含，我们直接把他拉出来当成根，做出一个菊花就可以了。

但是没有这么好的情况啊。我们随便钦定一个点当根，然后把其他的所有跟他在一个连通块里的，全部扔到这个树的第三层去。如果没有点了，那就是无解。

剩下所有点，就扔到第二层去，随便找一个第二层的点，作为第三层所有点的父亲即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;

struct node{
    int to,nxt;
}edge[N*2]; int head[N],cnt;
void add(int u,int v){
    edge[++cnt].to=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void adde(int u,int v){
    add(u,v); add(v,u);
}

int ae[N][2];
int res;
int tmpdot[N],tot;

int vis[N];
void dfs(int u,int f,int hd){//找连通块，这个hd没用
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to; if(v==f||vis[v]) continue;
        dfs(v,u,hd); tmpdot[++tot]=v;//tmpdot为第三层的点
    }
}

void fake_main(){
    memset(head,0,sizeof head);
    cnt=0; res=0; tot=0;
    memset(vis,0,sizeof vis);

    int n,m; cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        adde(u,v);
    }
    dfs(1,0,1); int flag=0;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            if(flag==0){
                for(int j=1;j<=tot;j++){
                    ae[++res][0]=i;
                    ae[res][1]=tmpdot[j];
                }
            }
            flag=1;
            ae[++res][0]=1;
            ae[res][1]=i;
        }
    }
    if(flag==0){
        cout<<"No\n"; return;
    }
    cout<<"Yes\n";
    for(int i=1;i<=res;i++){
        cout<<ae[i][0]<<" "<<ae[i][1]<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    int t; cin>>t;
    while(t--) fake_main();
}

/*
1
4 2
1 2
3 4
*/