题意

给出n对数，你可以操作n次，每次操作只能在下面三种中选择一种，问最多可以选多少个不同的数字。
  • 什么都不做
  • 如果a[i]以前没选过，那么可以选择a[i]
  • 如果b[i]以前没选过，那么可以选择b[i]

题解

想法很简单，就是一个并查集。
如果a[i]和b[i]的父亲一样，那么用一个数组记录一下这个父亲，说明这个堆里有环，否则把a[i]和b[i]合并，然后用map离散化（菜鸡懒惰的做法），计算每个堆里有多少不同的数字，如果这个堆里有环，就加上不同数字的个数，否则加上不同数字的个数-1。自己写几个数就看出来了。
对于环那个地方，为什么先用数组记录父亲呢，因为后边父亲可能会变，所以先记录下来，然后在找这个父亲的父亲就没问题了。可以参考下边的数据，1 3的时候父亲是3，到了5 6之后，父亲就变成6了。 
1
6
1 2
2 3
3 4
1 3
4 5
5 6
另外map会t，所以用unordered_map。

代码 

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

const int maxn=100100;
unordered_map<int,int> par,p,x,y,q,vis;

int Find(int x){
    if(x!=par[x])
        par[x]=Find(par[x]);
    return par[x];
}

void unite(int a,int b)
{
    int fa=Find(a);
    int fb=Find(b);
    if(fa!=fb)
        par[fa]=fb;
}

int a[maxn],b[maxn];
int c[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    int k=0;
    while(t--){
        memset(c,0,sizeof(c));
        par.clear();
        p.clear();
        x.clear();
        y.clear();
        q.clear();
        vis.clear();
        cout<<"Case #"<<++k<<": ";
        int n;
        cin>>n;
        int pos=0;
        int ans=0;
        for(int i=0;i<n;i++){
            cin>>a[i]>>b[i];
            par[a[i]]=a[i];
            par[b[i]]=b[i];
        }
        int kk=0;
        for(int i=0;i<n;i++){
            if(Find(a[i])==Find(b[i]))  c[kk++]=Find(a[i]);
            else unite(a[i],b[i]);
        }
        for(int i=0;i<kk;i++){
            p[Find(c[i])]=1;
        }
        for(int i=0;i<n;i++){
            int xx=Find(a[i]);
            int yy=Find(b[i]);
            if(!x[xx]) x[xx]=++pos,q[pos]=xx;
            if(!x[yy]) x[yy]=++pos,q[pos]=yy;
        }
        for(int i=0;i<n;i++){
            if(!vis[a[i]]) y[x[Find(a[i])]]++;
            vis[a[i]]=1;
            if(!vis[b[i]]) y[x[Find(b[i])]]++;
            vis[b[i]]=1;
        }
        for(int i=1;i<=pos;i++){
            if(!p[q[i]]) ans--;
            ans+=y[i];
        }
        cout<<ans<<endl;
    }
	return 0;
}