CF1559D2 题解

· · 题解

题解区怎么都是与一个点连边的题解？这里提供一个别的做法，应该更好想一些。

upd on 2024.4.12: 连通块大小的总和写错了，修改一下。

思路

先考虑 D1，猜想最多的操作次数就是 n-1-\max(m1,m2)，即一定可以一直连，直到一个森林变成树。证明就是考虑证明任意两个不是树的森林第一次都可以操作，而这个可以反证，如果不能操作则两棵树必定连通。如果第一次可以操作，则使用数学归纳法即可证明第一个结论。

因此现在只需要每次快速找到可以连边的点，而不需要决策了。对于 D1，直接枚举每个点对即可（因为如果当前点对连不了则以后也连不了，所以可以直接跳过）。

还有一个结论是，在某一棵树一个连通块中一定能选出来一个点连边。这个结论可以在下面的构造中看出来。

因为是集合总和有保证，所以可以想一些奇怪的根号做法。可以发现，每次拿出来最小的连通块，这些连通块大小的总和是 \mathcal O(n\sqrt{n}) 的。证明是考虑当连通块个数大于根号时最小的集合大小小于等于根号，当连通块个数小于等于根号时合并的个数小于等于根号。这些连通块大小的总和是 \mathcal O(n\log n) 的。因为这相当于启发式合并，最小的连通块在两个连通块中一定是较小的。

考虑第一棵树最小的连通块的点在第二棵树的连通块位置，设为 wz_1,wz_2,\cdots,wz_k。如果 wz 中有不同的数，则任选一个不在当前连通块的点去尝试匹配这两个不同的数，一定至少有一个不相同，即可连边。否则，在第二棵树中任选一个不是当前连通块的连通块即可连边。

使用 set 模拟上述过程即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
int fa[2][100010];
int find(int op,int x)
{
    while(x!=fa[op][x]) x=fa[op][x]=fa[op][fa[op][x]];
    return x;
}
vector<int> vec[100010];
struct Set
{
    int wz;
    bool operator < (Set x) const { return vec[wz].size()==vec[x.wz].size()?wz<x.wz:vec[wz].size()<vec[x.wz].size(); }
}; set<Set> q;
set<int> st;
int tot=0; pair<int,int> ans[100010];
bool vis[100010];
void merge(int x,int y)
{
    int fx=find(0,x),fy=find(0,y);
    q.erase({fx}),q.erase({fy});
    while(!vec[fx].empty()) vec[fy].push_back(vec[fx].back()),vec[fx].pop_back();
    fa[0][fx]=fy,q.insert({fy});
    fx=find(1,x),fy=find(1,y);
    fa[1][fx]=fy,st.erase(fx);
}
int main()
{
    cin>>n>>m1>>m2;
    for(int i=1; i<=n; ++i) fa[0][i]=fa[1][i]=i;
    for(int i=1; i<=m1; ++i)
    {
        int u,v; cin>>u>>v;
        fa[0][find(0,u)]=find(0,v);
    }
    for(int i=1; i<=m2; ++i)
    {
        int u,v; cin>>u>>v;
        fa[1][find(1,u)]=find(1,v);
    }
    for(int i=1; i<=n; ++i) vec[find(0,i)].push_back(i);
    for(int i=1; i<=n; ++i) if(i==fa[0][i]) q.insert({i});
    for(int i=1; i<=n; ++i) if(i==fa[1][i]) st.insert(i);
    while(q.size()>=2 && st.size()>=2)
    {
        vector<int> now=vec[(*q.begin()).wz];
        for(int i:now) vis[i]=1;
        int other=1; while(vis[other]) ++other;
        int fother=find(1,other);
        for(int i:now) vis[i]=0;
        int ffirst=find(1,now[0]);
        bool flag=0;
        for(int i=1; i<now.size(); ++i)
        {
            int fnow=find(1,now[i]);
            if(fnow!=ffirst)
            {
                if(fnow!=fother) ans[++tot]={now[i],other},merge(now[i],other);
                else ans[++tot]={now[0],other},merge(now[0],other);
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            auto wz=st.begin();
            if(*wz==ffirst) ++wz;
            ans[++tot]={now[0],(*wz)},merge(now[0],(*wz));
        }
    }
    cout<<tot<<'\n';
    for(int i=1; i<=tot; ++i) cout<<ans[i].first<<' '<<ans[i].second<<'\n';
    return 0;
}