朋友
题目背景
小明在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。
输出格式
一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）
输入输出样例
输入
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
输出
2
说明/提示
对于30%数据，N,M<=100，P,Q<=200
对于80%数据，N,M<=4000,P,Q<=10000.
对于全部数据，N,M<=10000,P,Q<=20000。
正解
我们可以用并查集来解决这个问题
m1=1集合中里面有多少个数字，m2=负1集合中里面有多少个数字
答案就是min(m1,m2);（原因都懂（不会的在评论区评论，我会解答））
并查集
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,p,q,a,b,m1,m2,pre[10005];
int find(int x)//找爸爸+路径压缩
{
if(pre[x]==0)return x;
return pre[x]=find(pre[x]);
}
void bcj(int x,int y)//并查集
{
int x1=find(x),y1=find(y);//找爸爸
if(x1!=y1)pre[y1]=x1;//爸爸不一样就合并
}
int main()
{
cin>>n>>m>>p>>q;
for(int i=1;i<=p;i++)
{
cin>>a>>b;
bcj(a,b);//并查集
}
a=find(1); //1集合最大的爸爸
for(int i=1;i<=n;i++)//从1开始，自己也要累加
if(a==find(i))m1++;//如果属于同一个集合，就累加
memset(pre,0,sizeof(pre));//记得清零，因为后面还要用
for(int i=1;i<=q;i++)
{
cin>>a>>b;
bcj(-a,-b);//并查集（前面要加“-”，让它变成正数，不然会越界）
}
a=find(1);//因为上面已经将负数变成正数了，所以不是find(-1),而是find(1)
for(int i=1;i<=m;i++)//从1开始，自己也要累加
if(a==find(i))m2++;//同一集合就累加
cout<<min(m1,m2); //找最小值
return 0;
}
京公网安备 11010502036488号