传送门：Interesting Computer Game
题解：
这个题目开始我分析的时候感觉有点像二分图的一个挪坑的一个操作，但是仔细一分析发现根本不可能拆成两个完全独立的子集，然后呢我就想到了最长公共子序列，每次拿到一个新的a，b就进行判断，然后向前面进行更新，但是弄出来以后才发现这个根本就是超时的，两秒钟，复杂度是O（n*logn），然后呢这个lis的算法就是一个O（n^2）的复杂度。后来问了以后才知道这个题目的做法是把每个点是否连接用先用邻接表存起来，然后呢用dfs在图上搜索，如果形成一个环，那么他就是全部用到了，如果是一个树的话就是用了n-1个。然后题目没说是一个连通图，所以要每个区域都遍历，最后把答案加起来
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<stack>
using namespace std;int ans = 0;
map<int, int> sign;
int head[200005];
int vis[200005];
int f[200005];int find(int x)
{if(x != f[x])x = f[x];return x;
}struct g{int next, v;
}edge[200005];
int cnt = 1;
int cnt1 = 1; void ini()
{sign.clear();for(int i = 0; i < 200005; i++){head[i] = -1; f[i] = i; } memset(vis, 0, sizeof(vis));cnt = 1;cnt1 = 1;ans = 0;
}void add(int x, int y)
{int u, v;if(!sign[x]){sign[x] = cnt1++;}u = sign[x]; if(!sign[y]){sign[y] = cnt1++;}v = sign[y];edge[cnt].v = v;edge[cnt].next = head[u];head[u] = cnt++;edge[cnt].v = u;edge[cnt].next = head[v];head[v] = cnt++;
}void dfs(int u, int fa, int&flag)
{for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].v;if(v == fa) continue;if(find(v) == find(u) ){flag = 1;continue;}f[v] = f[u];vis[v] = 1;dfs(v, u, flag);} return;
}int main()
{int t;scanf("%d", &t);for(int g = 1; g <= t; g++){ini();int n;scanf("%d", &n);int x, y;for(int i = 0; i < n; i++){scanf("%d %d", &x, &y);add(x, y);}for(int i = 1; i < cnt; i++){if(vis[i])continue;int flag = 0;dfs(i, 0, flag);if(flag){vis[i] = 1;}}for(int i = 1; i < cnt; i++)if(vis[i])ans++;printf("Case #%d: %d\n", g, ans);}}