https://codeforces.com/contest/2060/problem/E
题目大意
给出无向图 $F$ 和 $G$。可以对 F 进行操作：增加一条边或删除一条边的操作。
问至少需要多少次使得 $F$ 中任意两点 $u, v$ 有路径当且仅当 $G$ 中对应两点有路径。
给出 $F$ 和 $G$ 的点数 $n \ (\le 2 \times 10^5)$ 和各自的边数 $m_1, m_2 \ (0 \le m_1, m_2 \le 2 \times 10^5)$，以及所有的边。
简要题解
即要改变最少的边使得 $F$ 与 $G$ 的连通性一致。我们可以先用并查集处理 $G$ 的连通性，对于 $F$ 的边 $<u, v>$，假如 $G$ 中不连通，则一定不要，反之可以保留，因为要最少的改变，因此直接保留。
当处理完 $F$ 中所有应该保留的边之后，我们可以把这些边加入另外一个并查集。因为只处理了保留必要的边，却没保证 $G$ 中联通的 $F$ 中也联通，因此我们只需要看 $G$ 中的联通块数量比 $F$ 少多少即可。意味着还需增加差量的边，使得联通块数量一样。
其实这个题可以考一下输出方案（虽然很麻烦就是了）。
复杂度
$T$：$O(n \alpha (n))$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
struct UF {
int n;
int ns; // number of set
vector<int> fa,sz;
UF(int n_=0):n(n_),ns(n_),fa(n_),sz(n_,1) {
for(int i=0;i<n;i++) fa[i]=i;
}
void init(int n_) {
n=ns=n_; fa.assign(n,0); sz.assign(n,1);
for(int i=0;i<n;i++) fa[i]=i;
}
int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); }
bool same(int x,int y) { return find(x)==find(y); }
bool merge(int x,int y) {
x=find(x); y=find(y);
if(x==y) return false;
if(sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x]; fa[x]=y; ns--;
return true;
}
vector<vector<int>> getgrps() {
vector<int> id(n, -1);
vector<vector<int> > grps;
for (int i = 0; i < n; i++) {
if (id[find(i)] == -1) {
id[find(i)] = grps.size();
grps.emplace_back();
}
grps[id[find(i)]].push_back(i);
}
return grps;
}
};
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m1, m2; cin >> n >> m1 >> m2;
vector<int> ui(m1), vi(m1);
UF uf1(n), uf2(n);
for (int i = 0; i < m1; i++) {
cin >> ui[i] >> vi[i]; ui[i]--; vi[i]--;
}
int u, v;
for (int i = 0; i < m2; i++) {
cin >> u >> v; u--; v--;
uf2.merge(u, v);
}
int ans = 0;
for (int i = 0; i < m1; i++) {
u = ui[i]; v = vi[i];
if (uf2.same(u, v)) {
uf1.merge(u, v);
} else {
ans++;
}
}
ans += uf1.ns - uf2.ns;
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. Kevin and Arithmetic - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)