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);
    }
}