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;
}