题意：
给n个点对ai，bi，你已知所有点对的情况下，每轮如果ai或bi没用过，可以从ai和bi中选一个数，也可以不选择。
问最后能得到多少个数
做法：
把点对之间用一条边连起来建图。
可以发现答案 = 并查集个数 + （每个并查集内边数 - 1）
CODE
1 #include <bits/stdc++.h> 2 #define dbug(x) cout << #x << "=" << x << endl 3 #define eps 1e-8 4 #define pi acos(-1.0) 5 6 using namespace std; 7 typedef long long LL; 8 9 const int inf = 0x3f3f3f3f; 10 11 template<class T>inline void read(T &res) 12 { 13 char c;T flag=1; 14 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; 15 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; 16 } 17 18 const int maxn = 1e5 + 7; 19 20 int n, t; 21 int a[maxn], b[maxn]; 22 map<int, int> fa, vis; 23 int cnt, c[maxn]; 24 25 int fid(int x) { 26 return x == fa[x] ? x : fa[x] = fid(fa[x]); 27 } 28 29 int main() 30 { 31 read(t); 32 int cas = 0; 33 while(t--) { 34 read(n); 35 cnt = 0; 36 // memset(fa, 0, sizeof(fa)); 37 // memset(vis, 0, sizeof(vis)); 38 fa.clear(); 39 vis.clear(); 40 int ans = 0; 41 for ( int i = 1; i <= n; ++i ) { 42 read(a[i]); read(b[i]); 43 if(!fa[a[i]]) { 44 fa[a[i]] = (a[i]); 45 } 46 if(!fa[b[i]]) { 47 fa[b[i]] = (b[i]); 48 } 49 int fida = fid(a[i]), fidb = fid(b[i]); 50 // printf("fida:%d fidb:%d ",fida, fidb); 51 if (fida == fidb) 52 { 53 c[++cnt] = b[i]; 54 } 55 else { 56 ++ans; 57 // dbug(ans); 58 fa[fidb] = fida; 59 } 60 } 61 for ( int i = 1; i <= cnt; ++i ) { 62 // printf("c[%d]:%d ",i, c[i]); 63 int x = fid(c[i]); 64 if(!vis[x]) { 65 ++ans; 66 vis[x] = 1; 67 } 68 } 69 70 printf("Case #%d: ",++cas); 71 cout << ans << endl; 72 } 73 return 0; 74 }