同性公司情侣配对问题 - 最多能配成多少对情侣？ - 常规

同性公司情侣配对问题 - 最多能配成多少对情侣？

题目描述

有两个公司 A 和 B，这两个公司的员工有一个特点：一个公司的员工都是同性。

A公司有 N 名员工，其中有 P 对朋友关系。B公司有 M 名员工，其中有 Q 对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数 (Xi, Yi) 组成，表示朋友的编号分别为 Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是 1，小红的编号是 -1.

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入格式

第 1 行，4 个空格隔开的正整数 N, M, P, Q。

之后 P 行，每行两个正整数 Xi，Yi。

之后 Q 行，每行两个负整数 Xi，Yi。

输出格式

一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出样例

说明/提示

对于 30% 数据，N, M <= 100，P, Q <= 200

对于 80% 数据，N, M <= 4000, P, Q <= 10000.

对于全部数据，N, M <= 10000, P, Q <= 20000。

算法

(并查集, 贪心) $O(P+Q)$

先将 A 和 B 公司的员工区分开，对于 A 公司，将所有关系插入到同一个集合中，对于 B 公司同理。接着，对于小明和小红分别查找他们的关系所在的集合（注意小红的编号是负数，所以需要取绝对值），将两个集合合并。最后，遍历 A 公司和 B 公司中所有员工，统计每个集合中男女各有多少人，取最小值加入答案即可。

时间复杂度

对于每个操作，花费 $O(\alpha(N))$ 的时间，总时间复杂度为 $O(P+Q+\alpha(N)+\alpha(M))$，其中 $\alpha(N)$ 表示阿克曼函数的反函数。

参考文献

算法基础课第三章

C++ 代码

时间复杂度：$O(P+Q+\alpha(N)+\alpha(M))$

#include <iostream>
using namespace std;

const int MAXN = 10000 + 10;

int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    int n, m, p, q;
    cin >> n >> m >> p >> q;

    // 初始化并查集
    for (int i = 1; i <= n + m; i++) fa[i] = i;

    // 处理 A 公司的友谊关系
    for (int i = 0; i < p; i++) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }

    // 处理 B 公司的友谊关系
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        merge(-x, -y);
    }

    // 合并小明和小红所在的集合
    merge(1, -1);

    // 统计每个集合中男女人数
    int cnt_male = 0, cnt_female = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) == find(1)) cnt_male++;
    }
    for (int i = 1; i <= m; i++) {
        if (find(-i) == find(-1)) cnt_female++;
    }

    // 输出答案
    cout << min(cnt_male, cnt_female) << endl;
    return 0;
}