2020牛客暑期多校训练营（第八场）I.Interesting Computer Game(map离散化+并查集判环)
地址：https://ac.nowcoder.com/acm/contest/5673/I
题意：
n次，每次给出a,b;
可以进行三种操作：
1.不选
2.a如果之前没选过，可选a
3.b如果之前没选过，可选b
求可以获得的最大数目
解析：
首先用map进行一个离散化处理
假设把每次输入的看成一条边的话，可以推出：
对于每一个并查集块，大小为x，如果内部含环，就是x，否则为x-1
所以用并查集进行判环,c[]进行标记，如果c[]==1，说明它所在块含有环。
#include<bits/stdc++.h> #include<iostream> #include<cstring> #include<string.h> #include<cmath> #include<vector> #include<map> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=1e5+20; int pr[2*maxn],c[2*maxn]; //假设a[]和b[]每个数都不同，最多需要2*maxn的空间 int a[maxn],b[maxn]; int tot; int find(int x) { if(x!=pr[x]) return pr[x]=find(pr[x]); return x; } void init() { for(int i=1;i<=tot;i++) pr[i]=i,c[i]=0; } int main() { int t; scanf("%d",&t); int ac=1; while(t--) { int n; scanf("%d",&n); map<int,int>m; tot=1; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); if(!m[a[i]])m[a[i]]=tot++; if(!m[b[i]])m[b[i]]=tot++; } tot--; int sum=tot; init(); for(int i=1;i<=n;i++) { int x=find(m[a[i]]),y=find(m[b[i]]); if(x!=y) { pr[x]=y; if(c[x]||c[y]) //x并到y上，所以它俩只要有环，本并查集块就含环，标记一下。 c[y]=1; } else c[y]=1; } // cout<<sum<<"-"<<endl; for(int i=1;i<=tot;i++) { if(i==pr[i]&&!c[i]) sum--; //非环，-- } printf("Case #%d: %d ",ac++,sum); } }