题解：P11486 「Cfz Round 5」Mata rainen

_sin_ · 2024-12-29 19:47:00 · 题解

先将题目提供的 m 对点对连边，这样会连出来一个森林，如果不是森林必然无解。

考虑如何将这几个森林合并成一棵树。钦定一个连通块中最小的点为这个连通块的根，然后分类讨论两个连通块的合并。

1. 两个连通块的大小都大于一：\ 设两个连通块的根节点分别为 x,y。在 y 中任意选择一条边，设这条边的两个端点是 u,v，断开这条边。再让 x,u 和 x,v 连一条边。这样显然满足要求。
2. 两个连通块的大小只有一个等于一： 设两个连通块的根节点分别为 x,y。在 x 中任意选择一条边，设这条边的两个端点是 u,v，断开这条边。再让 y,u 和 y,v 连一条边。这样显然满足要求。
3. 两个连通块大小都等于一：\ 因为 m\ge 1，所以这种情况是可以规避掉的。

连通块使用并查集维护一下即可，时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;
int n,m,fa[N],hd[N],X[N],Y[N];
vector<pair<int,int> >ans,vec[N];
vector<int>tmp,sb[N];

int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}
void merge(int x, int y){x=find(x),y=find(y);if(x<y)swap(x,y);fa[x]=y;}

bool cmp(int x,int y){return sb[x].size()>sb[y].size();}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        if(x>y)swap(x,y);X[i]=x,Y[i]=y;
        if(find(x)==find(y))return puts("No"),0;
        merge(x,y);
    }
    for(int i=1;i<=n;i++)sb[find(i)].emplace_back(i);
    for(int i=1;i<=n;i++)if(fa[i]==i){
        sort(sb[i].begin(),sb[i].end());
        for(int x:sb[i])hd[x]=sb[i][0];
    }
    for(int i=1;i<=m;i++)vec[hd[X[i]]].emplace_back(X[i],Y[i]);
    for(int i=1;i<=n;i++)if(hd[i]==i)tmp.emplace_back(i);
    sort(tmp.begin(),tmp.end(),cmp);
    for(int i=1;i<tmp.size();i++){
        int u=tmp[0],v=tmp[i];
        // printf("%d %d\n",i,v);
        if(vec[v].empty()){
            // printf("%d %d ",u,v);
            // printf("%d \n",vec[u][0].second);
            vec[u].emplace_back(v,vec[u][0].second);
            vec[u][0].second=v;
        }else{
            vec[v].emplace_back(u,vec[v][0].second);
            vec[v][0].second=u;
        }
    }
    for(int x:tmp)for(auto p:vec[x])ans.emplace_back(p);
    puts("Yes");
    for(auto p:ans)printf("%d %d\n",p.first,p.second);
    return 0;
}