原题链接：https://ac.nowcoder.com/acm/contest/5673/I

题目描述

Apollo正在玩电脑游戏，该游戏共有n轮，Apollo共要玩T次。
每一轮中，系统会给出两个整数 和 ，而Apollo每轮可以执行以下三个操作中的一个：

• 什么也不做；
• 如果在先前的操作中未选择 ，那么Apollo可以选择；
• 如果在先前的操作中未选择 ，那么Apollo可以选择。

由于Apollo已经破解了游戏（啊这，该操作可能导致其他玩家体验感降低），在游戏开始之前就知道了每轮给出的数是多少。现在Apollo想知道他可以选择的最多的整数的数量。

输入描述

第一行给出一个整数T，表示测试样例的数量（即Apollo玩的次数）；
对于每个测试样例，第一行输入一个整数n，接下来的n行均给出n对数字 ，。

输出描述

对于每个测试样例，输出格式为：Case #x: y。
其中x指测试样例的编号，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

题解思路

首先看数据范围，a与b的上限均为 ，明显暴搜是不行的，所以需要进行离散化。
然后。。。就在WA/MLE/T了无数次后。。。被dalao告知可以用图论/并查集做。
然，作为蒟蒻直到现在也没有想出图论怎么做。。
下面就讲一下并查集的思路。
在离散化后开始查找与是否有同一祖先，即是否存在环，并用数组记录一下祖先。若二者没有同一祖先，则计算不同的数字的数量。
最后再判断一下，如果在某个或某几个堆中不存在环，那么每次找到不存在时 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n,fa[200010];
long long a[100050],b[100050],ls[200050],nt[200050];
long long ans,cnt;
int find(int x)//并查集
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{

    int T,cnT=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i],&b[i]);
            ls[cnt++]=a[i];
            ls[cnt++]=b[i];
        }
        sort(ls,ls+cnt);//离散化
        cnt=unique(ls,ls+cnt)-ls;
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(ls,ls+cnt,a[i])-ls;
            b[i]=lower_bound(ls,ls+cnt,b[i])-ls;
        }
        for(int i=0;i<cnt;i++)
        {
            fa[i]=i;
            nt[i]=0;
        }
        for(int i=1;i<=n;i++)//查找
        {
            if(find(a[i])!=find(b[i]))
            {
                nt[find(b[i])]|=nt[find(a[i])];
                fa[find(a[i])]=find(b[i]);
            }
            else
            {
                nt[find(a[i])]=1;
            }
        }
        ans=cnt;
        for(int i=0;i<cnt;i++)
            if(find(i)==i&&!nt[find(i)])//判断是否存在环
                ans--;
        printf("Case #%d: ",++cnT);
        printf("%lld\n",ans);
    }
}