Codeforces Round #738 (Div. 2) D. Mocha and Diana

https://codeforces.com/contest/1559/problem/D2
给你两组森林结构，现在分别在两组森林结构中把任意两个节点连接起来，重复这样的操作若干次，要求经过若干次操作以后形成的两组结构仍然分别是森林（无环）

• $easy$版本范围只有$1e3$，时间复杂度可以达到$O(n^2)$，创建两个并查集，初始状态先分好，之后暴力枚举每两个点，如果发现某一组森林中出现环，那么这条边不能连，否则连上，统计答案即可
• 问题的关键在于$hard$版本，现在数据范围达到了$1e5$，那么我们不能暴力了，怎么办呢？可以考虑一种启发式合并，把所有的节点都以较小编号的节点作为祖先，最终把所有集合都合并到祖先节点$1$上面去，这样就不是两个两个点暴力枚举，而是从前往后递推，使用两个指针$i$和$j$分别标记两个森林中的节点，如果已经和$1$号节点在一个分支里面就跳过，否则将他们和$1$号节点放到一个集合中并以$1$为根，同时统计答案即可，这样的时间复杂度就是并查集的$O(log(n))\times$一圈$for$的$O(n)$，最终复杂度是$O(nlog(n))$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
int fa1[MAXN], fa2[MAXN];
int mark1[MAXN], mark2[MAXN];
int FIND1(int x){
    return x == fa1[x] ? x : fa1[x] = FIND1(fa1[x]);
}
int FIND2(int x){
    return x == fa2[x] ? x : fa2[x] = FIND2(fa2[x]);
}
vector<pair<int, int> > ans;
int main(){
    #ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios::sync_with_stdio(false);int n, m1, m2, u, v;cin >> n >> m1 >> m2;for(int i=1;i<=n;i++){
    fa1[i] = fa2[i] = i;}for(int i=1;i<=m1;i++){
    cin >> u >> v;u = FIND1(u);v = FIND1(v);if(u < v) swap(u, v);fa1[u] = v;}for(int i=1;i<=m2;i++){
    cin >> u >> v;u = FIND2(u);v = FIND2(v);if(u < v) swap(u, v);fa2[u] = v;}for(int i=2;i<=n;i++){
    if(FIND1(i) != 1 && FIND2(i) != 1){
    fa1[FIND1(i)] = fa2[FIND2(i)] = 1;ans.push_back(make_pair(1, i));}}for(int i=1, j=1;i<=n;i++){
    if(FIND1(i) == 1) continue;while((FIND2(j) == 1) && j <= n) ++j;if(j <= n){
    fa1[i] = fa2[j] = 1;ans.push_back(make_pair(i, j));}}cout << ans.size() << '\n';for(int i=0;i<ans.size();i++) cout << ans[i].first << ' ' << ans[i].second << '\n';return 0;
}