洛谷P2078 朋友

题目传送门：洛谷P2078 朋友

题目详情：

小明在 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

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

输出 #1

2  

 题目分析：

又是一道并查集的题目，关于并查集的一些基础操作可以先看一下这一篇并查集模板题的文章（虽说本题也差不多是道模板题）：洛谷P1551 亲戚题解

本题可以先将A公司的员工用并查集来将小明的朋友（男）个数找出来，然后再用同样的方法将B公司中小红的朋友（女）个数找出来，然后再判断最多能形成多少对夫妻（实行一夫一妻制，否则无答案）。题目还是很简单的，但是小红公司员工的数据是用负数输入的，而c++数组在正常情况下是不能储存负数的（除非用一些特殊操作），因此在解题时我在题目要求的最大数据下多开了1倍的数组空间，然后在小明公司员工后面将小红公司的员工进行初始化确保小红公司员工由负数转为正数后不会和小明公司的员工数据重叠。

本题中用并查集的操作代码如下：

void init(int n)//初始化
{
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        height[i] = 1;//初始设所有元素的秩为1
    }
}
int find(int x)//查找-路径压缩
{
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y)//按秩合并
{
    x = find(x);//先找到要合并的x和y的根节点
    y = find(y);
    if (height[x] == height[y])//两个树的深度相同
    {
        height[x]++;//树的秩+1
        fa[y] = x;
    }
    if (height[x] < height[y])//x树的深度小于y树
        fa[x] = y;//将y设为x的父节点(把x合并到y中)
    if (height[x] > height[y])
        fa[y] = x;//将x设为y的父节点
}

判断最多能形成多少对夫妻（假设小明认识的朋友数为8，小红认识的朋友数为6，然后最多能形成的夫妻对数就是6对）一夫一妻！：

int judge(int x, int y)//判断
{
    return x > y ? y : x;//判断x是否大于y，大于返回y的值，小于则返回x的值
}

c++完整代码（已ac）:

#include<iostream>
const int Max = 20010;
using namespace std;
int fa[Max], height[Max];
int n, m, p, q;
void init(int n)//初始化
{
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        height[i] = 1;//初始设所有元素的秩为1
    }
}
int find(int x)//查找
{
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y)//合并
{
    x = find(x);//先找到要合并的x和y的根节点
    y = find(y);
    if (height[x] == height[y])//两个树的深度相同
    {
        height[x]++;//树的秩+1
        fa[y] = x;
    }
    if (height[x] < height[y])//x树的深度小于y树
        fa[x] = y;//将y设为x的父节点(把x合并到y中)
    if (height[x] > height[y])
        fa[y] = x;//将x设为y的父节点
}
int judge(int x, int y)//判断
{
    return x > y ? y : x;
}
int main()
{
    cin >> n >> m >> p >> q;//输入n个男员工和m个女员工以及p对朋友关系和q对朋友关系
    init(n + m);//员工总数为A公司员工加上B公司员工
    for (int i = 1; i <= p + q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (i <= p)//合并A公司男员工
        {
            if (find(x) != find(y))//如果两员工根节点不同则将两个员工合并
                merge(x, y);
        }
        else//合并B公司女员工
        {
            x *= -1;
            y *= -1;
            if (find(x + n) != find(y + n))//x+n确保女员工的值不会和前面的男员工的值重叠
                merge(x + n, y + n);
        }
    }
    int a = 0, b = 0;
    for (int i = 1; i <= n; i++)
        if (find(i) == find(1))//如果和小明认识则小明的朋友加1
            a++;
    for (int i = n + 1; i <= n + m; i++)//如果和小红认识则小红的朋友加1
        if (find(i) == find(n + 1))//n+1为小红
            b++;
    cout << judge(a, b);//输出最多能够形成几对夫妻
    return 0;
}

本来最初是想用按秩合并后树的深度height【1】和height【n+1】（1为小明，n+1为小红）比较后输出答案的，但是只过了2个测试点，然后才明白这是不对的，因为小明或小红认识的朋友数应该为树的叶子节点的个数，犯了个小错误。