[开发测试]codeforces 1559D1 Mocha and Diana (Easy Version)

链接：

https://codeforces.com/problemset/problem/1559/D1

题意：

摩卡和戴安娜各有n个树林，编号从1到n，初始各有m对关系，将n个树林两两相连，连起来的树林成为一个森林。想要再添加其他连接，并且没有循环，最多可以再加多少连接。

本题，用并查集，然后暴力，每次找到没有连接的两片森林，就将他们连在一起。

代码如下：

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<string.h>
#include<random>
using namespace std;
typedef long long ll;
int prem[1003];
int pred[1003];
vector<pair<int, int>>vec;
int findm(int x) {
	if (prem[x] == x) {
		return x;
	}
	return prem[x] = findm(prem[x]);
}
int findd(int x) {
	if (pred[x] == x) {
		return x;
	}
	return pred[x] = findd(pred[x]);
}
void joinm(int x, int y) {
	int fx = findm(x), fy = findm(y);
	if (fx != fy) {
		prem[fy] = fx;
	}
}
void joind(int x, int y) {
	int fx = findd(x), fy = findd(y);
	if (fx != fy) {
		pred[fy] = fx;
	}
}
int main() {
	int n;
	cin >> n;
	int m1, m2;
	cin >> m1 >> m2;
	int u, v;
	for (int i = 0; i <= 1000; i++) {
		prem[i] = i;
		pred[i] = i;
	}
	for (int i = 0; i < m1; i++) {
		cin >> u >> v;
		joinm(u, v);
	}
	for (int i = 0; i < m2; i++) {
		cin >> u >> v;
		joind(u, v);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int um = findm(i), vm = findm(j);
			int ud = findd(i), vd = findd(j);
			if (um != vm && ud != vd) {
				vec.push_back({ i,j });
				joinm(um, vm);
				joind(ud, vd);
			}
		}
	}
	cout << vec.size() << endl;
	for (auto i : vec) {
		cout << i.first << " " << i.second << endl;
	}
	return 0;
}