朋友

GitHub跳转原题关系图返回列表

分别求出 A 公司里与 1 号同组的人数、B 公司里与 -1 号同组的人数，答案就是这两个连通块大小的较小值。

OJ: luogu

题目 ID: P2078

难度:入门

标签:并查集模拟

日期: 2026-06-20 00:07

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有两个公司：

  • A 公司员工编号是正数
  • B 公司员工编号是负数

同一个公司里给出若干对朋友关系，而且“朋友的朋友还是朋友”。

已知小明编号是 1，小红编号是 -1，他们彼此认识。现在问：

  • 通过小明和小红认识的人里
  • 最多能配成多少对异性情侣

包括他们自己。

思路

先看一个小数据暴力：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n, m, p, q;
vector<int> ga[MAXN], gb[MAXN];
bool vis[MAXN];

int bfs_count(vector<int> g[], int start, int limit) {
    for (int i = 1; i <= limit; i++) {
        vis[i] = false;
    }

    queue<int> que;
    que.push(start);
    vis[start] = true;
    int cnt = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        cnt++;

        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                que.push(v);
            }
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p >> q;

    for (int i = 1; i <= n; i++) {
        ga[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        gb[i].clear();
    }

    for (int i = 1; i <= p; i++) {
        int x, y;
        cin >> x >> y;
        ga[x].push_back(y);
        ga[y].push_back(x);
    }

    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        x = -x;
        y = -y;
        gb[x].push_back(y);
        gb[y].push_back(x);
    }

    int cnt_a = bfs_count(ga, 1, n);
    int cnt_b = bfs_count(gb, 1, m);

    cout << min(cnt_a, cnt_b) << '\n';
    return 0;
}

暴力直接把两个公司的朋友关系各自建成无向图：

  • 在 A 公司里从 1 出发 BFS，统计和小明同组的人数
  • 在 B 公司里从 -1 出发 BFS，统计和小红同组的人数

因为一个公司里所有人性别相同，所以最后真正能配成的情侣数，只取决于：

  • 小明这边认识了多少人
  • 小红这边认识了多少人

两边一一配对，答案就是这两个数量的较小值。

正式做法可以直接用并查集维护传递性的朋友关系。

分别对两个公司开两个并查集：

  1. 读 A 公司的 p 对朋友关系，合并正数编号
  2. 读 B 公司的 q 对朋友关系，因为输入是负数编号，先转成正下标再合并
  3. 最后统计：
    • size(1)：A 公司里和小明同组的人数
    • size(1)：B 公司里和小红同组的人数（把 -1 转成 1 后）

答案就是：

min(小明所在集合大小, 小红所在集合大小)

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

struct DSU {
    int fa[MAXN], sz[MAXN];

    void init(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }

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

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        fa[y] = x;
        sz[x] += sz[y];
    }

    int size(int x) {
        return sz[find(x)];
    }
};

int n, m, p, q;
DSU dsu_a, dsu_b;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p >> q;
    dsu_a.init(n);
    dsu_b.init(m);

    for (int i = 1; i <= p; i++) {
        int x, y;
        cin >> x >> y;
        dsu_a.unite(x, y);
    }

    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        x = -x;
        y = -y;
        dsu_b.unite(x, y);
    }

    cout << min(dsu_a.size(1), dsu_b.size(1)) << '\n';
    return 0;
}

复杂度

设 A 公司有 N 人，B 公司有 M 人，朋友关系分别有 P,Q 对。

并查集的总复杂度为：

O((N+M+P+Q) α(N+M))O((N+M+P+Q)\,\alpha(N+M))

空间复杂度 O(N+M)O(N + M)。

总结

这题的关键是别被“情侣配对”这个表述带偏。朋友关系有传递性，真正要求的只是两个连通块大小，然后取较小值而已。