RT

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

样例输入 #1

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

样例输出 #1

2

提示

对于 $30 \%$ 的数据，$N,M \le 100$，$P,Q \le 200$；

对于 $80 \%$ 的数据，$N,M \le 4 \times 10^3$，$P,Q \le 10^4$；

对于 $100 \%$ 的数据，$N,M \le 10^4$，$P,Q \le 2 \times 10^4$。

附上蒟蒻的代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+7;
ll f[N],n,m,p,q,y,x,s1,s2;
ll find(ll x)
{
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
int main()
{
	cin>>n>>m>>p>>q;
	for(int i=1;i<=m+n+1;i++)f[i]=i;
	for(int i=1;i<=p;i++)
	{
		cin>>x>>y;
		ll fx=find(max(x,y));
		ll fy=find(min(x,y));
		if(fx!=fy)f[fx]=fy;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>x>>y;
		ll fx=find(max(-x+n,-y+n));
		ll fy=find(min(-x+n,-y+n));
		if(fx!=fy)f[fx]=fy;
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==f[1])s1++;
	}
	for(int i=n+1;i<=m+n+1;i++)
	{
		if(f[i]==f[1+n])s2++;
	}
//	cout<<s1<<" "<<s2;
	cout<<min(s1,s2);
}