博客园食用链接：https://www.cnblogs.com/lonely-wind-/p/13435543.html
题目大意：给你T组数据，每组数据给你n对数，分别表示为
，你每次都可以取其中的一个，但如果之前
已经被取过了，就不能再取了，
也是一样的。那么问你总共可以取多少种不同的数。
输入
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
emmm，开局就跑了波网络流。。。T了，后面nb队友过的。事实上我们可以将这些关系画出来，我们会发现，对于一个关系组，如果里面有环的话那么能够取得的数字就是整个图的大小，否则的话就只能取其大小-1个。至于判断有环无环，我们直接判断每次出现的两个数字是否有共同的祖先就可以了，然后我们可以传递这种关系。不过由于 比较大，所以我们要离散化一下，各位应该写得比较熟练了，先sort一下再unique一下，接着二分一下就完事了。不过注意的是father等并查集需要用到的数组也需要开到2倍空间大小。。。。我就因为这个卡了好久QAQ。。。
以下是AC代码：
#include <bits/stdc++.h>
using namespace std;const int mac=1e5+10;
const int inf=1e9+10;int au[mac],av[mac];
int num[mac<<1],father[mac<<1],bk[mac<<1];
int sz[mac<<1],lu[mac],lv[mac];int find(int x){return x==father[x]?x:father[x]=find(father[x]);}int main()
{int t;scanf ("%d",&t);for (int cse=1; cse<=t; ++cse){int n,cnt=0;scanf ("%d",&n);for (int i=1; i<=n; i++){scanf ("%d%d",&au[i],&av[i]);num[++cnt]=au[i],num[++cnt]=av[i];}sort(num+1,num+1+cnt);int it=unique(num+1,num+1+cnt)-num;for (int i=1; i<=n; i++){lu[i]=lower_bound(num+1,num+it,au[i])-num;lv[i]=lower_bound(num+1,num+it,av[i])-num;}int ans=0;for (int i=1; i<it; i++) father[i]=i,bk[i]=0,sz[i]=1;for (int i=1; i<=n; i++){int u=lu[i],v=lv[i];int fu=find(u),fv=find(v);if (fu!=fv){father[fu]=fv;sz[fv]+=sz[fu];bk[fv]=max(bk[fv],bk[fu]);}else {bk[fv]=1;}}for (int i=1; i<it; i++){if (father[i]!=i) continue;ans+=sz[i]-1;if (bk[i]) ans++;}printf ("Case #%d: %d\n",cse,ans);}return 0;
}