cf div3 998 E(并查集）

E :
给出两个简单无向图 （没有重边和自环）f g .
可以对f 进行 删边 和加边 的操作。问至少操作多少次 ，使得 f 和 g 的 点的联通情况相同（并查集的情况相同）

首先思考删边 ：
对于 我 f 图存在边 e ，只要这个边 所连接的两个点 在g 中是不联通的，那么这条边一定要删除。

现在的问题是，所有要删的边 都删除了吗》答案是 Yes.
对于两个点 a b ，如果他们之间联通但不是直接通过 直接的一条边。那么我path 中的边，一定在我遍历e 的时候，删掉了。

所以到现在为止 删边的操作 已经完成了。
现在考虑加边的操作：
加边的数量 可以通过 连通块的数量的差值 直接计算。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
struct DSU {vector<int> p, siz;DSU(int n) : p(n + 1), siz(n + 1, 1) {iota(p.begin(), p.end(), 0);// 会将容器 p 中的元素依次赋值为 0, 1, 2, 3, ...，直到填满整个范围。}int find(int x) {while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩return x;}bool same(int x, int y) {return find(x) == find(y);}bool uno(int x, int y) {x = find(x), y = find(y);if (same(x, y)) return false;siz[x] += siz[y];p[y] = x;return true;}int size(int x) {return siz[find(x)];}
};
void solve()
{int n,m1,m2;cin>>n>>m1>>m2;int u,v;vector<PII>e1(m1);for (int i=0;i<m1;i++){cin>>e1[i].first>>e1[i].second;}DSU dsu1(n),dsu2(n);for (int i=0;i<m2;i++){cin>>u>>v;dsu2.uno(u,v);}int res=0;for (auto [u,v]:e1){if (!dsu2.same(u,v)){res++;}else dsu1.uno(u,v);}int siz1=0,siz2=0;for (int i=1;i<=n;i++){siz1+= dsu1.find(i)==i;siz2+= dsu2.find(i)==i;}res+=siz1-siz2;cout<<res<<"\n";
}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;cin>>t;while (t--){solve();}return 0;
}