牛客多校第八场 I题 Interesting Computer Game

题目大意是每次给你两个数，你只能在其中选一个没有选过的数，可以不选。问你最多选多少个数

我们可以把两个数当成一条边，由于数字会很大，所以先离散化。然后就转化成了一个图的问题。

题目意思等价于在图中有若干条边，对于每条边，你可以选择它所连接的两个顶点中的一个，问你最多可以选择多少个不同的点。

我们知道整个输入数据转化成图后，肯定是由若干个联通的图组成的。我们就单独对一个联通图考虑。

我们设一个联通图有n个点，联通代表着它最少有n-1条边。n-1条边你能选多少个点嘞，显然是n-1个。为啥嘞，你可以把这个图想象成一个有根树，只要我们不选根，那么它剩下的节点我们都可以选，而且只有n-1条边代表着我们只能选n-1次。如果大于n-1条边呢？显然可以选n个点。n-1条边的时侯我们没办法选根，那么多的几条边中，我们随便选一条，再在这条边上随便选一个点当根，就可以把根选到了。

所以就转化为判断联通图中边的数量是否大于n-1条，若是则可以选n个，反之选n-1个。再加上所有联通图的答案即可。

渣渣代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
vector<int> ve;
int getid(int x) {
  return lower_bound(ve.begin(), ve.end(), x) - ve.begin();
}
vector<int> ed[N];
int x[N], y[N], ans;
bool vis[N];
int bian, num;
void dfs(int x) {
  bian += ed[x].size();
  num++;
  for(auto it : ed[x]) {
    if(!vis[it]) {
      vis[it] = 1;
      dfs(it);
    }
  }
}
void solve(int i) {
  bian = 0;
  num = 0;
  vis[i] = 1;
  dfs(i);
  bian /= 2;
  if(bian >= num) ans += num;
  else ans += num - 1;
}
int main() {
  int t; read(t);
  for(int ca = 1; ca <= t; ca++) {
    int n; read(n);
    ve.clear();
    ans = 0;
    int cn = 0;
    _rep(1, n, i) {
      read(x[i]), read(y[i]);
      ve.push_back(x[i]);
      ve.push_back(y[i]);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    int len = ve.size();
    _for(0 , len, i) ed[i].clear(), vis[i] = 0;
    _rep(1, n, i) {
      x[i] = getid(x[i]);
      y[i] = getid(y[i]);
      ed[x[i]].push_back(y[i]);
      ed[y[i]].push_back(x[i]);
    }
    for(int i = 0; i < len; i++) {
      if(!vis[i]) {
        solve(i);
      }
    }
    printf("Case #%d: %d\n", ca, ans);
  }
}