Interesting Computer Game

原题请看这里

题目描述：

阿波罗 ( A p o l l o ) (Apollo) (Apollo)正在玩有趣的电脑游戏。 游戏中有 N N N个回合，每回合，计算机会给 A p o l l o Apollo Apollo两个整数 ( a i (a_i (ai​和 b i ) b_i) bi​)，并且 A p o l l o Apollo Apollo可以执行以下三个动作之一。

• 阿波罗无能为力。
• 如果之前所有回合都未选择整数 a i a_i ai​，则 A p o l l o Apollo Apollo可以选择整数 a i a_i ai​。
• 如果在之前的所有回合中都未选择整数 b i b_i bi​，则 A p o l l o Apollo Apollo可以选择整数 b i b_i bi​。

阿波罗 ( A p o l l o ) (Apollo) (Apollo)破解了比赛，在比赛开始之前，他已经知道了每一轮的所有候选号码。 现在他想知道最佳策略可以选择的最大整数数。我相信这对您来说是一个非常简单的问题，请帮助 A p o l l o Apollo Apollo解决此问题。

输入描述：

第一行是整数 T ( 1 ≤ T ≤ 10 ) \mathbf{T}(1 \leq \mathbf{T} \leq 10) T(1≤T≤10)，它是测试用例的数量。
每个测试用例均以包含正整数 N ( 1 ≤ N ≤ 1 0 5 ) N(1 \le N \le 10 ^ 5) N(1≤N≤105)的行开头，指示此游戏中的回合数。
接下来 N N N行。 第 i i i行包含两个整数 a i a_i ai​和 b i ( 1 ≤ a i ≤ 1 0 9 ， 1 ≤ b i ≤ 1 0 9 ) b_i(1 \le a_i \le 10 ^ 9，1 \le b_i \le 10 ^ 9) bi​(1≤ai​≤109，1≤bi​≤109)，表示第 i i i个回合的两个整数。

输出描述：

对于每个测试用例，输出一行包含 C a s e Case Case # x x x: y y y的行，其中 x x x是测试用例编号，而 y y y是答案。

样例输入：

2
6
1 2
2 3
3 4
1 4
1 3
2 4
5
1 2
1 2
1 3
2 3
5 6

样例输出：

Case #1: 4
Case #2: 4

思路：

并查集。（听说图论也可以做）
刚开始看到这道题还以为就是简单的 t a n tan tan，结果队友 W A WA WA了好几遍才发现是道图论…
首先，我们需要将数据离散化，不然数据太大数组会越界。
然后，我们判断一下 a i a_i ai​和 b i b_i bi​的祖先是否一样，即判断是否有环，用一个数组记录一下祖先。
如果不一样，那么就计算一下有多少个不同的数字。
答案就是所有堆中的不重复的数字之和，如果没有环就 a n s − − ans-- ans−−

A C AC AC C o d e Code Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int t,n,a[MAXN],ls[MAXN],v[MAXN],sum,ans,fa[MAXN],bian[MAXN];
int find(int x){
	if(fa[x]==x) return x;
	int w=fa[x];
	fa[x]=find(fa[x]);
	v[x]+=v[w];
	bian[x]+=bian[w];
	return fa[x];
}
int main(){
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a[i],&a[i+n]);
			ls[i]=a[i];
			ls[i+n]=a[i+n];
		}
		sort(ls+1,ls+n*2+1);
		ans=sum=unique(ls+1,ls+n*2+1)-ls-1;
		memset(v,0,sizeof(v));
		for(int i=1;i<=n*2;i++){
			a[i]=lower_bound(ls+1,ls+sum+1,a[i])-ls;
			v[a[i]]++;
		}//离散化
		for(int i=1;i<=sum;i++){
			fa[i]=i;
			bian[i]=1;
		}
		for(int i=1;i<=n;i++){
			int fax=find(a[i]),fay=find(a[i+n]);
			if(fax^fay){
				v[fax]+=v[fay];
				bian[fax]+=bian[fay];
				fa[fay]=find(a[i]);
			}
		}
		for(int i=1;i<=sum;i++)
			if(find(i)==i&&bian[i]*2-2==v[i])
				ans--;
		printf("Case #%d: %d\n",Case,ans);
	}
}