P10179 题解

_Flame_ · 2024-02-20 07:57:00 · 题解

\text{solution}

比较简单的构造题。

考虑点 u_i 和点 v_i 之间恰有两条边的限制意味着什么，发现这意味着点 u_i 和点 v_i 的父亲节点相同。

考虑用并查集将所有父节点相同的节点合并，这样可以得到若干个集合，显然，当只出现了一个集合时，构造无解。

接下来处理集合之间如何连边，发现对于一个集合 S_i 我们将其中的点全部连向另一个集合 S_j 中的一个点是合理的，于是对于所有不是 S_j 的集合，我们都将其连到 S_j 中的一个点上，对于 S_j 中的其他点，将其连到任意点 i 使得 i 不在集合 S_j 中即可。

\text{code}

int n,m;

int fa[maxn];
int siz[maxn];

int find(int a){
    if(fa[a]==a){
        return fa[a];
    }
    return fa[a]=find(fa[a]); 
}

void merge(int a,int b){
    int na=find(a),nb=find(b);
    if(na==nb){
        return ;
    }
    fa[na]=nb;
    siz[nb]+=siz[na];
}

map<int,int> mp;

int cnt[maxn],tot;

void solve(){
    for(int i=1;i<=n;i++){
        cnt[i]=0;
    }
    mp.clear();
    tot=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        merge(u,v);
    }
    if(siz[find(1)]==n){
        puts("No");
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!mp[find(i)]){
            mp[find(i)]=1;
            cnt[++tot]=find(i);
        }
    }
    puts("Yes");
    int flag=0;
    for(int i=1;i<=n;i++){
        if(find(i)!=cnt[1]){
            flag=i;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        if(find(i)!=cnt[1]){
            printf("%lld %lld\n",i,cnt[1]);
        }
        else if(i==find(i)){
            continue ;
        }
        else{
            printf("%lld %lld\n",i,flag);
        }
    }
    return ;
}