CF1559D2 Mocha and Diana (Hard Version) 题解 贪心

· · 题解

\large\text{题目传送门}

\text{Description}

\text{Solution}

很好的贪心题。

不妨令 A 图连通块个数不小于 B 图。

我们证明 B 图最后连通块个数为 1。

若 A 连通块数量大于 1，若此时无法操作，考虑到 A 图中连通块 a，b。

对于 a，b 中的点，他们在 B 图中一定连通。

那么考虑到 A 中所有连通块，可发现 B 全连通，即连通块数量为 1。

由此贪心分析可知，随意加可行边即可。

因此 D1 就可以直接暴力枚举点对加边即可，时间复杂度 O(n^2\alpha(n))。

考虑优化贪心。

考虑一个中心点 s。

我们先让所有点与 s 尝试连边。

然后连完后令 A 图中与 s 不连通的点集为 L，B 图中与 s 不连通的点集为 R。

显然 L\cap R=\varnothing。

考虑 l\in L 和 r\in R。

由定义有 A 图中 l 与 s 不连通，r 与 s 连通，B 图相反。

那么任意 l 与 r 都可连边。

然后只要随意配对完 L 或 R 就行了，此时一幅图变成一个连通块。

时间复杂度 O(n\alpha(n))。

\text{Code}

我写的 O(n\log n) 的并查集，没加按秩合并。

const int N=1e5+5;
int n,m1,m2,fa1[N],fa2[N],ans,qaq[N][2],l[N],r[N],cnt1,cnt2;

inline int find1(int x){return fa1[x]==x?x:fa1[x]=find1(fa1[x]);}
inline void merge1(int x,int y){fa1[find1(x)]=find1(y);}

inline int find2(int x){return fa2[x]==x?x:fa2[x]=find2(fa2[x]);}
inline void merge2(int x,int y){fa2[find2(x)]=find2(y);}

// ---------- DSU ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    rd(n);rd(m1);rd(m2);
    for(re i=1;i<=n;++i) fa1[i]=fa2[i]=i;
    for(re i=1;i<=m1;++i){
        int x,y;rd(x);rd(y);merge1(x,y);
    }
    for(re i=1;i<=m2;++i){
        int x,y;rd(x);rd(y);merge2(x,y);
    }
    for(re i=2;i<=n;++i)
        if(find1(i)!=find1(1)&&find2(i)!=find2(1)) qaq[++ans][0]=i,qaq[ans][1]=1,merge1(i,1),merge2(i,1);
    for(re i=2;i<=n;++i)
        if(find1(i)!=find1(1)) l[++cnt1]=i,merge1(i,1);
        else if(find2(i)!=find2(1)) r[++cnt2]=i,merge2(i,1);
    wr(ans+min(cnt1,cnt2));puts("");
    for(re i=1;i<=ans;++i) wr(qaq[i][0]),putchar(' '),wr(qaq[i][1]),puts("");
    for(re i=1;i<=min(cnt1,cnt2);++i) wr(l[i]),putchar(' '),wr(r[i]),puts("");
    return 0;
}

// ---------- Main ---------- //