[开发测试]Codeforces Round #738 (Div. 2)_D1. Mocha and Diana (Easy Version)

D1. Mocha and Diana (Easy Version)

题目传送门：

题目传送门

题面：

题目大意：

给定$n$个点，以及m1和m2。
m1，m2分别代表在图1中连了m1条边，在图二中连了m2条边（无向图）。输出最多还能在图中连多少条边，不会让图变成有环图。

本次连边采取同步连法，即选定u,v，在两张图内一起连u,v。
l两张图本身互不影响。

本题复杂度松，可以直接并查集暴力维护。

代码：

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e3 + 10;
int p1[maxn]; //存储每个点的祖宗节点
int p2[maxn]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find1(int x) {
    if (p1[x] != x) p1[x] = find1(p1[x]);
    return p1[x];
}

int find2(int x) {
    if (p2[x] != x) p2[x] = find2(p2[x]);
    return p2[x];
}

int main() {
    int n, m1, m2;
    int u, v;
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1; i <= n; i++) {
        p1[i] = p2[i] = i;
    }
    for (int i = 0; i < m1; i++) {
        scanf("%d %d", &u, &v);
        p1[find1(u)] = find1(v);
    }
    for (int i = 0; i < m2; i++) {
        scanf("%d %d", &u, &v);
        p2[find2(u)] = find2(v);
    }
    vector<pair<int, int> > ans;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (find1(i) != find1(j) && find2(i) != find2(j)) {
                ans.push_back({i, j});
                p1[find1(i)] = find1(j);
                p2[find2(i)] = find2(j);
            }
        }
    }
    printf("%d\n", ans.size());
    for (auto i:ans)
        printf("%d %d\n", i.first, i.second);
}