传送门
题目大意
有T组数据，每组数据有n对数每对数只能选择一个数或者不选，且前面没有选过相同的数，最后保证找到的数最多。
题解
我们将每对数连成一条边，每次只能选边上的一个顶点，n对数连成一个图，图分为以下两种情况
- 连成一棵树，那么n个点n-1条边中我们最多只能选n-1个点，因为每组数据中我们最多只能选一个
- 连成一个环，那么环上所有点都可以选择，包括与环连接的连通图上所有顶点
那么我们就需要一个布尔数组circle来判断这个点是否是在环内，如果遇到两个点的祖先结点相同那么就说明他们在一个环内，如果不相同就将两者合并
完整代码
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>using namespace std;typedef long long ll;
const int N = 2e5 + 100;
unordered_map<int,int> mp;
int cnt,f[N];
bool cicle[N];int Find(int x)//查找祖先结点
{if(f[x] == x){return x;}else{return f[x] = Find(f[x]);}
}void Union(int x, int y)
{int xx = Find(x);int yy = Find(y);if(xx != yy) //如果父结点不相等就合并{f[xx] = yy;cicle[yy] |= cicle[xx];//或等于，将两者的或运算结果赋给cicle[y]，只有两者都为树时合并才为树}else{cicle[xx] = true;//如果相等证明是一个环，所有顶点都可以算进去}
}void Init()
{mp.clear();cnt = 0;for(int i = 0 ; i < N; i++){f[i] = i;cicle[i] = false;}
}int main()
{int t,Case = 0;cin >> t;while(t--){Init();int n;scanf("%d",&n);for(int i = 1 ; i <= n ; i++){int x,y;scanf("%d %d",&x,&y);if(!mp[x]){mp[x] = ++cnt;}if(!mp[y]){mp[y] = ++cnt;}Union(mp[x],mp[y]);}int ans = cnt;for(int i = 1 ; i <= cnt ; i++){if(f[i] == i && !cicle[i])//如果遇到一棵树{ans--;}}printf("Case #%d: %d\n",++Case,ans);}return 0;
}