2020牛客暑期多校训练营（第八场）——Interesting Computer Game
样例输入
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
题目大意
阿波罗正在玩有趣的电脑游戏。 游戏中有N轮。
在每个回合中，计算机将为阿波罗提供两个整数ai和bi，并且阿波罗只能刚好执行一次以下三个操作之一。
1.不做任何操作。
2.如果之前所有回合都未选择整数ai，则阿波罗可以选择整数ai。
3.如果之前所有回合都未选择整数bi，则阿波罗可以选择整数bi。
阿波罗破解了比赛，在比赛开始之前，他已经知道了每一轮的所有候选号码。 现在，他想知道可以使用最佳策略选择的最多整数数。我相信这对您来说是一个非常简单的问题，请帮助阿波罗解决这个问题。
第一行是整数T(1≤T≤10)，测试用例的数量。
每个测试用例以正整数N(1≤N≤10^5)开头，表示回合数。
然后，N行跟随。第i行包含两个整数ai和bi(1≤ai,bi≤10^9)，表示第i个回合的两个整数。
对于每个测试用例，输出包含的一行，其中x是测试用例编号，y是答案。
解题思路
并查集
首先，我们需要将数据离散化，不然数据太大数组会越界。
然后，我们判断一下aii?和bi的祖先是否一样，即判环，用一个数组记录一下祖先。
如果不一样，那么就计算一下有多少个不同的数字。
答案就是所有堆中的不重复的数字之和，如果没有环就输出ans
AC Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+100;
int f[MAXN],a[MAXN],b[MAXN],l[MAXN],d[MAXN],sz[MAXN];
int find(int x)
{if(f[x]==x) return x;int fa=f[x];f[x]=find(f[x]);d[x]+=d[fa];sz[x]+=sz[fa];return f[x];
}
int main()
{int t,n,m,l_l,ans;scanf("%d",&t);for(int K=1;K<=t;K++){scanf("%d",&n);m=0;memset(l,0,sizeof(l));for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);l[++m]=a[i];l[++m]=b[i];}memset(d,0,sizeof(d));sort(l+1,l+1+m);l_l=unique(l+1,l+1+m)-l-1;for(int i=1;i<=n;i++){a[i]=lower_bound(l+1,l+1+l_l,a[i])-l;b[i]=lower_bound(l+1,l+1+l_l,b[i])-l;//离散化d[a[i]]++;d[b[i]]++;}for(int i=1;i<=l_l;i++) f[i]=i,sz[i]=1;for(int i=1;i<=n;i++){int fa=find(a[i]),fb=find(b[i]);if(fa!=fb){sz[fa]+=sz[fb];d[fa]+=d[fb];f[fb]=fa;}}ans=l_l;for(int i=1;i<=l_l;i++)if(find(i)==i&&sz[i]*2-2==d[i])ans--;printf("Case #%d: %d\n",K,ans);}
}