给出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了。

另外map会t，所以用unordered_map。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 const int maxn=100100;

 5 unordered_map<int,int> par,p,x,y,q,vis;

 6

 7 int Find(int x){

 8     if(x!=par[x])

 9         par[x]=Find(par[x]);

10     return par[x];

11 }

12

13 void unite(int a,int b)

14 {

15     int fa=Find(a);

16     int fb=Find(b);

17     if(fa!=fb)

18         par[fa]=fb;

19 }

20

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

22 int c[maxn];

23

24 int main()

25 {

26     ios::sync_with_stdio(false);

27     cin.tie(0);

28     cout.tie(0);

29     int t;

30     cin>>t;

31     int k=0;

32     while(t--){

33         memset(c,0,sizeof(c));

34         par.clear();

35         p.clear();

36         x.clear();

37         y.clear();

38         q.clear();

39         vis.clear();

40         cout<<"Case #"<<++k<<": ";

41         int n;

42         cin>>n;

43         int pos=0;

44         int ans=0;

45         for(int i=0;i<n;i++){

46             cin>>a[i]>>b[i];

47             par[a[i]]=a[i];

48             par[b[i]]=b[i];

49         }

50         int kk=0;

51         for(int i=0;i<n;i++){

52             if(Find(a[i])==Find(b[i]))  c[kk++]=Find(a[i]);

53             else unite(a[i],b[i]);

54         }

55         for(int i=0;i<kk;i++){

56             p[Find(c[i])]=1;

57         }

58         for(int i=0;i<n;i++){

59             int xx=Find(a[i]);

60             int yy=Find(b[i]);

61             if(!x[xx]) x[xx]=++pos,q[pos]=xx;

62             if(!x[yy]) x[yy]=++pos,q[pos]=yy;

63         }

64         for(int i=0;i<n;i++){

65             if(!vis[a[i]]) y[x[Find(a[i])]]++;

66             vis[a[i]]=1;

67             if(!vis[b[i]]) y[x[Find(b[i])]]++;

68             vis[b[i]]=1;

69         }

70         for(int i=1;i<=pos;i++){

71             if(!p[q[i]]) ans--;

72             ans+=y[i];

73         }

74         cout<<ans<<endl;

75     }

76     return 0;

77 }