题意：给出n对元组<a, b>每次可以选择a或者b或者不选，问最多可以选择出多少种不同的数字。n<1e5, a,b<1e9
题解：把数字离散化化成点，存在<a,b>则a，b之间加边，对于一个联通分量，如果含有环则对答案的贡献是sz，否则是sz-1。注意：这题有一个离散化，开并查集数组的时候应该开双倍，初始化也是同样，还有就是别忘记了合并的时候有一方已经含有环的情况。
#include <bits/stdc++.h> #define IO_read ios::sync_with_stdio(false);cin.tie(0) #define fre freopen("C:\in.txt", "r", stdin) #define _for(i,a,b) for(int i=a; i< b; i++) #define _rep(i,a,b) for(int i=a; i<=b; i++) #define inf 0x3f3f3f3f #define lowbit(a) ((a)&-(a)) using namespace std; typedef long long ll; template <class T> void read(T &x) { char c; bool op=0; while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1; x=c-'0'; while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0'; if(op) x=-x; } const int maxn=2e5+5; //段错误一次 int T, n, kase, a[maxn], b[maxn], c[maxn]; int fa[maxn], having[maxn], sz[maxn]; int find_fa(int x) { if(fa[x]==x) return x; return fa[x]=find_fa(fa[x]); } int main() { read(T); while(T--) { read(n); //_rep(i, 1, n) fa[i]=i, sz[i]=1, having[i]=0; WA了一次 _rep(i, 1, n) read(a[i]), read(b[i]), c[2*i-1]=a[i], c[2*i]=b[i]; sort(c+1, c+1+2*n); int cnt=unique(c+1, c+1+2*n)-c-1; _rep(i, 1, cnt) fa[i]=i, sz[i]=1, having[i]=0; _rep(i, 1, n){ a[i]=lower_bound(c+1, c+1+cnt, a[i])-c; b[i]=lower_bound(c+1, c+1+cnt, b[i])-c; } _rep(i, 1, n){ int f1=find_fa(a[i]), f2=find_fa(b[i]); if(f1!=f2){ fa[f2]=f1, sz[f1]+=sz[f2]; if(having[f2]) having[f1]=1; //这里漏写了 } else{ having[f1]=1; } } int ans=0; _rep(i, 1, cnt) if(find_fa(i)==i) ans+=sz[i]-1+having[i]; printf("Case #%d: %d ", ++kase, ans); } return 0; }