[开发测试]D2. Mocha and Diana (Hard Version) (并查集+思维)

PS:这题官方好像给的要启发式合并？代码太长了感觉有点劝退，其实这题可以有更简单的做法。除了这个做法，好像还有大佬用随机化过的，我没看懂，但我大受震撼，ORZ

题解：首先当两个点不在同一棵树内时我们一定可以连条边，这就是并查集的合并。最后我们连的边一定是连到了一棵树上，我们先固定这棵树，将所有可以连的树全部连到1这个树上（当且仅这个点所在的两片森林中都不在这棵树上时才连）。然后剩下还没连到这棵棵树上的点在两片森林中只有一种情况，即一个连了一个没连。这时候连森林1的和以直接连森林2的点连（画图显而易见），我们用两个set分别记录这些点，然后直接连就行。说的有点模糊，具体见代码。
AC代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+5;
int n,m1,m2;
int p1[N],p2[N];

int find(int p[],int x){
	if(p[x]!=x) return p[x]=find(p,p[x]);
	return p[x];
}

void merge(int p[],int a,int b){
	p[find(p,a)]=find(p,b);
}

bool same(int p[],int a,int b){
	return find(p,a)==find(p,b);
}

int main(){
	cin>>n>>m1>>m2;
	for(int i=0;i<=n+10;i++)p1[i]=i,p2[i]=i;
	while(m1--){
		int a,b;
		cin>>a>>b;
		merge(p1,a,b);
	}
	while(m2--){
		int a,b;
		cin>>a>>b;
		merge(p2,a,b);
	}
	
	vector<PII>ans;
	for(int i=2;i<=n;i++){
		if(!same(p1,1,i)&&!same(p2,1,i))
		{
			ans.push_back({1,i});
			merge(p1,1,i);
			merge(p2,1,i);
		}
	}
	
	set<int>s1,s2;
	for(int i=2;i<=n;i++){
		if(!same(p1,1,i)) s1.insert(find(p1,i));
		if(!same(p2,1,i)) s2.insert(find(p2,i));
	}
	
	for(auto a=s1.begin(),b=s2.begin();a!=s1.end()&&b!=s2.end();a++,b++){
		ans.push_back({*a,*b});
	}
	
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++)cout<<ans[i].x<<" "<<ans[i].y<<endl;
	
}