小明在A公司工作小红在B公司工作。题目描述这两个公司的员工有一个特点：一个公司的员工都是同性。A公司有N名员工其中有P对朋友关系。B公司有M名员工其中有Q对朋友关系。朋友的朋友一定还是朋友。每对朋友关系用两个整数XiYi组成表示朋友的编号分别为XiYi。男人的编号是正数女人的编号是负数。小明的编号是1小红的编号是-1大家都知道小明和小红是朋友那么请你写一个程序求出两公司之间通过小明和小红认识的人最

算法

(并查集,贪心) $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))$

C++ 代码