P10179 题解

cppcppcpp3 · 2024-02-19 22:02:33 · 题解

Link

构造题。

对于限制 (u,v)，不妨先收紧一点，认为是 u,v 的父节点相同。于是对限制 (u,v) 和限制 (u,w)，v 和 w 的父亲都与 u 的相同，可以合并成一个集合 S=\{u,v,w\}，S 中的点有相同的父节点。

这样最终会得到若干个集合 S_i。显然最终如果只有一个集合，不存在合法构造，因为没有点作为公共的父亲；否则考虑以下的构造方案：

• 先选出某个集合的某个点，不妨选择点 1，其所在集合为 S_1。把点 1 作为这个公共的父亲。

• 将其它集合的每个点分别和点 1 连边，这样其它集合的限制就满足了。

• 最后选出其它集合中的任意一点 x，把 S_1 中除 1 外的所有点分别和 x 连边。这样满足了 S_1 内所有点都通过 x 互相联系。

最终形成的树如图所示：

实现上用并查集维护即可。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=3e5+5;
const int inf=1e9+7;

inline int wrd(){
    int x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){x=x*10+c-48,c=getchar();}
    return x*f;
}

int n,m,fa[N];
int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]);}
void unity(int x,int y){
    fa[find(x)]=find(y);    
}

vector<pii> as;

void solve(){
    n=wrd(),m=wrd(),as.clear();
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i){
        int u=wrd(),v=wrd();
        unity(u,v);
    }

    int c=0;

    for(int i=1;i<=n;++i) c+=(i==find(i));
    if(c<2) return puts("No"),void();

    c=0;

    for(int i=1;i<=n;++i){
        if(find(1)==find(i)) continue;
        as.push_back({1,i}),c=i;
    }
    for(int i=2;i<=n;++i){
        if(find(1)==find(i)) as.push_back({c,i});
    }
    puts("Yes");
    for(auto x:as) printf("%d %d\n",x.fi,x.se);
}

signed main(){
    int T=wrd();
    while(T--) solve();
    return 0;
}