题目大意

一个游戏有N个回合，每回合提供两个整数ai和bi，每回合只能选以下三个操作之一。

  1. 不做任何操作。
  2. 如果ai没被选过（指ai的数值），可以选择ai。
  3. 如果bi没被选过，可以选择bi。

先给出所有a1,a2,...,an与b1,b2,...,bn，求出选择的最多整数数量。

解题思路

第一种思路

我们用一个并查集来解决这个问题，操作如下：
如果ai和bi的父亲一样，即堆中有环，我们就用数组来记录这里的父亲（父亲一直在变，所以这里先数组记录，后面再找这个父亲的父亲解决问题）；
否则，我们把ai和bi合并，计算每个堆里有多少不同的数字。

我们的答案就是每个堆中数（不重复）的个数，如果一个堆里没有环就再减去1。

第二种思路

  • 我们可以将每组ai,bi两个数连上一条边，这道题就可以转化成一个图的问题。
    所以，题意可以转化为：给定一张点权图，对于图中每条边可以选择两个顶点中的一个，求最多可以选多少个值不同的点。

  • 显而易见，所有的a与b所构成的图，肯定是由若干连通的块组成的。
    所以，我们对每个连通块考虑。
    设一个连通块有n个点，因此它最少有n-1条边，在这种情况下，我们最多可以选的点数是n-1个；而在边多于n-1时，我们就可以选全部的n个点了。
    如果把这个图想象成一个有根树，在边数大于n-1条时，我们在多出的边中随便选一条，在这条边定一个根，就可以选根了。

  • 综上，我们这个问题就转化为了：
    在每个连通图中，边的数量大于n-1条就选n个，否则选n-1个，统计所有图之和。

    AC代码

    代码用的第一种思路+用map来离散化。

    #include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],b[N],f[N*2];
bool c[N*2];
map<int,int> m;
int find(int x)
{
  if(f[x]!=x) f[x]=find(f[x]);
  return f[x];
}
int main()
{
  int T,n,t,ans,x,y,i,j;
  scanf("%d",&T);
  for(j=1;j<=T;j++)
  {
      t=0;m.clear();
      scanf("%d",&n);
      for(i=0;i<n;i++)
      {
          scanf("%d%d",&a[i],&b[i]);
          if(!m[a[i]]) m[a[i]]=++t;
          if(!m[b[i]]) m[b[i]]=++t;
      }
      for(i=1;i<=t;i++) c[i]=0,f[i]=i;
      for(i=0;i<n;i++)
      {
          x=find(m[a[i]]),y=find(m[b[i]]);
          if(x!=y)
          {
              f[x]=y;
              if(c[x]||c[y]) c[y]=1,c[x]=0;
          }
          else c[y]=1;
      }
      ans=t;
      for(i=1;i<=t;i++)
          if(f[i]==i && !c[i]) ans--;
      printf("Case #%d: %d\n",j,ans);
  }
  return 0;
}