【洛谷】P2078 朋友

题目链接：P2078 朋友 – 洛谷

思路

这道题思路很简单，建立A公司和B公司的并查集，遍历小明认识的人ans1和小红认识的人ansB，然后输出min(ansA, ansB)即可

代码

//
// Created by xiaoeyv on 2025/6/18.
//

#define maxn 10010
#include<bits/stdc++.h>
using namespace std;

int n, m, p, q;

int preA[maxn], rA[maxn],
        preB[maxn], rB[maxn];

int find(int x, int *pre) {
    return pre[x] == x ? x : pre[x] = find(pre[x], pre);
}

void join(int x, int y, int *pre, int *r) {
    int rx = find(x, pre), ry = find(y, pre);
    if (rx == ry)
        return;
    if (r[rx] < r[ry])
        pre[rx] = ry;
    else {
        pre[ry] = rx;
        if (r[rx] == r[ry])
            r[rx]++;
    }
}

int ansA = 0, ansB = 0;

int main() {
    cin >> n >> m >> p >> q;
    // init
    for (int i = 0; i <= n; i++) {
        preA[i] = i;
    }
    for (int i = 0; i <= m; i++) {
        preB[i] = i;
    }
    memset(rA, 0, sizeof(rA));
    memset(rB, 0, sizeof(rB));
    while (p--) {
        int x, y;
        cin >> x >> y;
        join(x, y, preA, rA);
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        join(-x, -y, preB, rB);
    }
    int rootA = find(1, preA);
    int rootB = find(1, preB);
    for (int i = 1; i <= n; i++)
        if (find(i, preA) == rootA)
            ansA++;
    for (int i = 1; i <= m; i++)
        if (find(i, preB) == rootB)
            ansB++;
    cout << min(ansA, ansB) << endl;
    return 0;
}