朋友

题目背景

小明在 A 公司工作，小红在 B 公司工作。

题目描述

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

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

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

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

输入格式

输入的第一行，包含 \(4\) 个空格隔开的正整数 \(N,M,P,Q\)。

之后 \(P\) 行，每行两个正整数 \(X_i,Y_i\)。

之后 \(Q\) 行，每行两个负整数 \(X_i,Y_i\)。

输出格式

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

样例 #1

样例输入 #1

4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3

样例输出 #1

2

提示

对于 \(30 \%\) 的数据，\(N,M \le 100\)，\(P,Q \le 200\)；

对于 \(80 \%\) 的数据，\(N,M \le 4 \times 10^3\)，\(P,Q \le 10^4\)；

对于 \(100 \%\) 的数据，\(N,M \le 10^4\)，\(P,Q \le 2 \times 10^4\)。

题解

这题还是套模板
不过，给的数据竟然用正负号区分男女？？
因此，这里我采用了新定义一个数gen来区分男女。

代码

#include<iostream>
using namespace std;
int n, m, p, q; int x, y;
int pre1[10010], pre2[10010];


int root(int x, int gen);
void merge(int x, int y, int gen);


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

    //初始化，员工只和自己有朋友关系
    for (int i = 1; i <= 10005; i++) {
        pre1[i] = i;
        pre2[i] = i;
    }

    //合并A 公司朋友关系
    for (int i = 1; i <= p; i++){
        cin >> x >> y;
        merge(x, y, 1);
    }

    //合并B 公司朋友关系
    for (int i = 1; i <= q; i++)
    {
        cin >> x >> y;
        merge(-x, -y, 2);//由于B公司员工性别为女，编号为负，所以要取反
    }

    //统计与小明（编号为1）和小红（取反编号为1）的朋友关系数量
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= 10005; i++) {
        cnt1+=root(i, 1)==root(1, 1);
        cnt2+=root(i, 2)==root(1, 2);
    }

    // 输出能够配成的情侣对数
    cout << min(cnt1, cnt2) << endl;

    return 0;
}

void merge(int x, int y, int gen)
{
    x = root(x, gen);y = root(y, gen);
    if (x == y)return;
    else if(gen == 1)pre1[y] = x;
    else if(gen == 2)pre2[y] = x;
}


int root(int x, int gen)
{
    if (gen == 1)
        return  pre1[x] = pre1[x] == x ? x : root(pre1[x], gen);

    else if (gen == 2)
        return pre2[x] = pre2[x] == x ? x : root(pre2[x], gen);
}

奇怪的是，题设给的n和m我怎么没用到？无所谓了( ᖛ ̫ ᖛ )ʃ)