朋友(AC in luogu P2078)
题目背景
小明在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
输出样例#1:
2
说明
对于30%数据,N,M<=100,P,Q<=200
对于80%数据,N,M<=4000,P,Q<=10000.
对于全部数据,N,M<=10000,P,Q<=20000。
Solution
简单的并差集问题,只要在模组上稍作改动。
显然有:
1.需建立两个族谱。
par1[maxn];
par2[maxn];
2.第二个族谱中将负数序号转换为正数。
x=-x;
y=-y;
3.保证两个族谱中与1有亲缘关系的元素的祖宗都是1。只要在连接亲缘关系时,保证序号较小的是祖宗就好了。
if(x<y){
par[y]=x;
}
else{
par[x]=y;
}
得到代码如下
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10001,maxp=20001;
int par1[maxn],par2[maxn];
int n,m,p,q;
int can1=0,can2=0;
inline void pre_treat(){
for(int i=1;i<=n;i++) par1[i]=i;
for(int i=1;i<=m;i++) par2[i]=i;
}
inline int find1(int x){
if(par1[x]==x) return x;
else{
return par1[x]=find1(par1[x]);
}
}
inline int find2(int x){
if(par2[x]==x) return x;
else{
return par2[x]=find2(par2[x]);
}
}
inline void unite1(int x,int y){
x=find1(x);
y=find1(y);
if(x==y) return ;
if(x<y){
par1[y]=x;
return ;
}
par1[x]=y;
}
inline void unite2(int x,int y){
x=find2(x);
y=find2(y);
if(x==y) return ;
if(x<y){
par2[y]=x;
return ;
}
par2[x]=y;
}
int main(){
scanf("%d%d%d%d",&n,&m,&p,&q);
pre_treat();
for(int i=1;i<=p;i++){
int x,y;scanf("%d%d",&x,&y);
unite1(x,y);
}
for(int i=1;i<=q;i++){
int x,y;scanf("%d%d",&x,&y);
x=-x; y=-y;
unite2(x,y);
}
for(int i=1;i<=n;i++){
if(find1(i)==1){
can1++;
}
}
for(int i=1;i<=m;i++){
if(find2(i)==1){
can2++;
}
}
printf("%d\n",min(can1,can2));
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)