[开发测试]Codeforces-738 Mocha and Diana (Easy Version)

题目大意：给定两个森林，在其中一个图中加边的同时另一个图也会加上相应的边，边不允许重复，求最大加边数量并输出加边的起点与终点

1.可以用两个并查集来存储每个图的集合关系

2.数据范围 n < 1e3 可以暴力 n 方枚举

3.枚举从1~n每个点对(i,j)，如果在两个并查集中同时满足find(i) != find(j)，那么可以将答案++并记录在答案中（贪心？）

#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"*"<<endl
const int maxn = 1e5 + 8;
int fa1[maxn];
int fa2[maxn];
int n, m1, m2;
struct node
{
	int u, v;
};
queue<node> q;
void init()
{
	for (int i = 1; i <= n; i++)
	{
		fa1[i] = i;
		fa2[i] = i;
	}
}
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]);
}
void Union1(int u, int v)
{
	int f1 = find1(u);
	int f2 = find1(v);
	if (f1 != f2)
		fa1[f1] = f2;
}
void Union2(int u, int v)
{
	int f1 = find2(u);
	int f2 = find2(v);
	if(f1 != f2)
		fa2[f1] = f2;
}
int main()
{
	int cnt = 0;
	cin >> n >> m1 >> m2;
	init();
	for (int i = 1; i <= m1; i++)
	{
		int u, v;
		cin >> u >> v;
		Union1(u, v);
	}
	for (int i = 1; i <= m2; i++)
	{
		int u, v;
		cin >> u >> v;
		Union2(u, v);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			int f1 = find1(i);
			int f2 = find1(j);
			int ff1 = find2(i);
			int ff2 = find2(j);
			if (f1 != f2 && ff1 != ff2)
			{
				cnt++;
				q.push({ i,j });
				Union1(i, j);
				Union2(i, j);
			}
		}
	}
	cout << cnt << endl;
	while (!q.empty())
	{
		cout << q.front().u << " " << q.front().v << endl;
		q.pop();
	}
	return 0;
}