题目链接：E. Graph Composition

写在前面

这场比赛前四道题很简单，半个小时就写完了，这道题卡了我1个多小时也没写出来~
赛时用的贪心，发现贪心并不是最优算法，赛后看了他人思路，发现这题用并查集写非常简单，思路挺巧妙的，还是我太菜了（bushi）

题意

给两个图 F 和 G，在 F 中删边或加边，使两图连通性相同。

思路

贪心思想：

• G中出现的两条边而F中不曾出现，则增边
• F中出现的两条边而G中不曾出现，则删边

这思路显然是错误的，它考虑的是联通性，并不是单纯判断边与边是否连接

既然要判断联通性，显然并查集可以将一张图切割成若干个联通块，我们只需要判断每个联通块中G和F是否相等即可

这题删边的话比较复杂，那么我们只需要在增边的时候不加上删去的边，让 $ans++$ 即可

首先让G图中的各点进行联通，然后在G图的并查集里遍历F图的所有边

• 如果这两条边的父节点相同，则在F图中增加这条边
• 不相同，让 $ans++$

接着在F图的并查集里遍历G图的所有边

• 如果这两条边的父节点相同，则继续循环
• 不相同，则在F图中增加这条边，让 $ans++$

最后输出 $ans$

code

const int N=2e5+5;
int a[N],b[N],c[N],d[N],f[N],g[N];
int find(int x,int fa[]){
	if(fa[x]==x) return x; 
	else return fa[x]=find(fa[x],fa);
}
void solve(){
	int n,m1,m2;
	cin >> n >> m1 >> m2;
	for(int i=1;i<=n;++i){
		f[i]=i,g[i]=i;
	}
	for(int i=1;i<=m1;++i){
		cin >> a[i] >> b[i];
	}
	for(int i=1;i<=m2;++i){
		cin >> c[i] >> d[i];
		g[find(c[i],g)]=g[find(d[i],g)];
	}
	int ans=0;
	for(int i=1;i<=m1;++i){
		if(g[find(a[i],g)]==g[find(b[i],g)]){
			f[find(a[i],f)]=f[find(b[i],f)];
		}
		else ans++;
	}
	for(int i=1;i<=m2;++i){
		if(f[find(c[i],f)]!=f[find(d[i],f)]){
			f[find(c[i],f)]=f[find(d[i],f)];
			ans++;
		}
	}
	cout << ans << endl;
	return ;
}