题目
思路：
性质1：能在结点u，v添加边的充要条件是u，v在第一个图和第二个图都不连通
性质2：可以添加的边数等于 n - 1 - max(m1, m2)，并且添加边的顺序不会影响结果（即 边（u，v）满足性质1，就可以直接添加，不会影响结果），证明如下：
对于hard version：先让所有可以与结点1连边的结点连边，然后对于结点2 ~ n，可以分为三类结点：在第一个图与结点1不连通，在第二个图与结点1连通（表示为01）、10 、11，（不存在00，若存在00，那么这个结点就会与结点1连边，变成11）。11的结点不能再连边，对答案无贡献，可以忽略；01的结点u可以与10的结点v连边，注意添加边（u，v）后，原本和u在第一个图中同一个连通块的结点（原本整个连通块的结点都是01）都会变成11，同理v在第二个图中所在连通块也是变成11，故对于每个连通块只找最高级祖先来连边。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e18, maxm = 4e4 + 5;
const int N = 1e6;
const int mod = 1e9 + 7;
// const int mod = 998244353;
//const __int128 mod = 212370440130137957LL;
// int a[1005][1005];
// bool vis[505][505];
int n, m;
int a[maxn];
int b[maxn];
string s;
struct DSU{
vector<int> fa, siz;
DSU(int n) : fa(n), siz(n, 1) {
for(int i = 0; i < n; i++){
fa[i] = i;
}
}
int find(int x){
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int u, int v){
if(find(u) != find(v)){
fa[find(u)] = find(v);
}
}
};
// struct Node{
// int a, b;
// // int val, id;
// bool operator<(const Node &u)const{
//
// }
// }node[maxn];
//long long ? maxn ? n? m?
void solve(){
int res = 0;
int k;
int m1, m2;
cin >> n >> m1 >> m2;
int u, v;
DSU t1(n + 5), t2(n + 5);
for(int i = 1; i <= m1; i++){
cin >> u >> v;
t1.merge(u, v);
}
for(int i = 1; i <= m2; i++){
cin >> u >> v;
t2.merge(u, v);
}
res = n - 1 - max(m1, m2);
cout << res << '\n';
for(int i = 2; i <= n; i++){
if(t1.find(i) != t1.find(1) && t2.find(i) != t2.find(1)){
t1.merge(i, 1);
t2.merge(i, 1);
cout << 1 << ' ' << i << '\n';
}
}
vector<int> vec[2];
for(int i = 2; i <= n; i++){
if(t1.find(i) != t1.find(1) && t1.find(i) == i){//01类的结点且是该连通块的最高级祖先
vec[0].pb(i);
}
if(t2.find(i) != t2.find(1) && t2.find(i) == i){//10类的结点且是该连通块的最高级祖先
vec[1].pb(i);
}
}
for(int i = 0; i < min(vec[0].size(), vec[1].size()); i++){
cout << vec[0][i] << ' ' << vec[1][i] << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
?
