CF1559D1 Mocha and Diana (Easy Version) 题解
KaisuoShutong
·
·
题解
CF1559D1 Mocha and Diana (Easy Version)
加强版题解
题意
两片森林，都有一些初始边。求以下操作的最多次数，使得图中无环，并输出方案。
操作：选择 x,y，在两片森林中分别连边。
### 题解
算法：枚举 $\forall i,j$，判断是否能够合并，最后输出答案。
用并查集实现的时间复杂度是 $O(n^2\times\alpha)$ 的。
正确性证明：
从过程态考虑或许会有些麻烦，我们直接考虑最终态。
> lemma. 最终态的两片森林中一定有至少一片是一颗树。
> 证明：
若第一片森林中只有一棵树，原命题得证。
故不妨设第一片森林有至少两颗树，设为 $A$ 和 $B$。考虑其中任意两个点 $a\in A$，$b\in B$。
若 $a$ 与 $b$ 在第二片森林中不属于同一棵树，那么可以再连边 $(a,b)$，与最终态定义矛盾。
故对于 $a\in A$，其与 $B$ 中所有点皆属于同一棵树。由此可得，$A$ 与 $B$ 在第二片森林中属于同一棵树。
同理可得，$A$ 中所有点在 $B$ 中皆属一棵树，原命题得证。
由此可知，无论使用什么样的顺序，最终状态的加边数都是一样的。
点个赞吧。
```cpp
//月亮照耀青窗，窗里窗外皆有青色的光。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
const int maxn = 100010;
int n,m1,m2,ans,a[maxn],f[maxn],g[maxn];vector<pair<int,int> >q;
int GF(int x) {return f[x]==x?x:f[x]=GF(f[x]);}
int gf(int x) {return g[x]==x?x:g[x]=gf(g[x]);}
signed main() {
n=read(),m1=read(),m2=read();
for(int i=1;i<=n;i++) f[i]=g[i]=i;
for(int i=1;i<=m1;i++) f[GF(read())]=GF(read());
for(int i=1;i<=m2;i++) g[gf(read())]=gf(read());
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(GF(i)^GF(j)&&gf(i)^gf(j)) {
f[f[i]]=f[j],g[g[i]]=g[j],q.push_back(make_pair(i,j));
}
cout<<q.size()<<'\n';
for(auto y:q) cout<<y.first<<' '<<y.second<<'\n';
return 0;
}
```