题目背景
小明在A公司工作,小红在B公司工作。
题目描述
这两个公司的员工有一个特点:一个公司的员工都是同性。
A公司有N名员工,其中有P对朋友关系。B公司有M名员工,其中有Q对朋友关系。朋友的朋友一定还是朋友。
每对朋友关系用两个整数(Xi,Yi)组成,表示朋友的编号分别为Xi,Yi。男人的编号是正数,女人的编号是负数。小明的编号是1,小红的编号是-1.
大家都知道,小明和小红是朋友,那么,请你写一个程序求出两公司之间,通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)
输入输出格式
输入格式:
第1行,4个空格隔开的正整数N,M,P,Q。
之后P行,每行两个正整数Xi,Yi。
之后Q行,每行两个负整数Xi,Yi。
输出格式:
一行,一个正整数,表示通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)
输入输出样例
输入样例#1:
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
说明
对于30%数据,N,M<=100,P,Q<=200
对于80%数据,N,M<=4000,P,Q<=10000.
对于全部数据,N,M<=10000,P,Q<=20000。
哎,两个饥渴全公全母的公司找朋友,方便进一步交往,毕竟在公司异性可见不到,貌似是小红比较好运,先找到了小明。大家此时可能都在感谢小红呢,帮助自己找到了那个他/她。
好,回到正题,找啊找啊找py,嘿嘿。
首先建立两个用于并查集的数组,俩人是朋友就联上关系(单纯的py关系);
建完以后,循环将每个人查询一遍,他是否与小红/小明有联系,取个min值。
:在此心疼被舍去的man/woman,幸福离你们不远,可它又离开了。
WLZ:哈哈哈,活该,我都这么大了,还单棍一直。(明显羡慕、嫉妒、恨)。
附上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
int n,m,a,b;
int fa[20001],f[20001];
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=n;i++)fa[i]=i;
int s,t;
for(int i=1;i<=a;i++)
{
scanf("%d%d",&s,&t);
int g=find(s);
int h=find(t);
if(g==1)
{
fa[h]=g;
continue;
}
if(h==1)
{
fa[g]=h;
continue;
}
fa[g]=h;
}
int man=0;
for(int i=1;i<=n;i++)if(find(i)==1)man++;
for(int i=1;i<=m;i++)fa[i]=i;
for(int i=1;i<=b;i++)
{
scanf("%d%d",&s,&t);
int g=find(s*(-1));
int h=find(t*(-1));
if(g==1)
{
fa[h]=g;
continue;
}
if(h==1)
{
fa[g]=h;
continue;
}
fa[g]=h;
}
int woman=0;
for(int i=1;i<=m;i++)if(find(i)==1)woman++;
printf("%d",min(man,woman));
}