题解：P11486 「Cfz Round 5」Mata rainen

先将题目提供的

m

对点对连边，这样会连出来一个森林，如果不是森林必然无解。

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

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

连通块使用并查集维护一下即可，时间复杂度

O(n\log n)

。

代码：

CPP

#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;
}

题解：P11486 「Cfz Round 5」Mata rainen

文章操作

相关推荐

评论

题解：P11486 「Cfz Round 5」Mata rainen