传送门:Interesting Computer Game

题意

给你n对数,在每对数当中只能选一个(或者不选),问最多能取多少个不同的数。

思路

用图论的思想建模。

这相当于是一个有重边的无向图。对于每个连通分量,如果其中存在环(重边也算环),那么就可以取出这个连通分量内的所有点;如果不存在环,那么可以把这个连通分量想象成是一条链,最后的点取不到,最多只能取出连通分量点数减1。

由于是无向图,要判断在连线的过程中是否出现了环,可以用并查集维护。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int x[N],y[N],t1[N],t2[N],fa[N],sz[N];
bool tag[N];
unordered_map<int,bool>vis;
vector<int>ans;
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        sz[i]=1;
        tag[i]=0; // i点祖先所在的集合是否有环
    }
}
int find_fa(int u)
{
    return fa[u]=(u==fa[u]?u:find_fa(fa[u]));
}
void join(int u,int v)
{
    int a=find_fa(u),b=find_fa(v);
    if(a==b)
    {
        tag[a]=1; // 两个点已经是同一集合,再连一条边,就是环
    }
    else
    {
        fa[a]=b;
        sz[b]+=sz[a];
        tag[b]|=tag[a]; // 把是否有环的信息传递给新祖先
        sz[a]=1;
        tag[a]=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int T,n,cas=0;
    cin>>T;
    while(T--)
    {
        cin>>n;
        vis.clear();
        ans.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>x[i]>>y[i];
            if(!vis[x[i]])
            {
                vis[x[i]]=1;
                ans.push_back(x[i]);
            }
            if(!vis[y[i]])
            {
                vis[y[i]]=1;
                ans.push_back(y[i]);
            }
            vis[x[i]]=1;
            vis[y[i]]=1;
        }
        sort(ans.begin(),ans.end());
        int cnt=ans.size(); // 离散化后有cnt个不同的数
        init(cnt);
        for(int i=1;i<=n;i++)
        {
            // 离散化,下标从1开始
            int t1=lower_bound(ans.begin(),ans.end(),x[i])-ans.begin()+1; 
            int t2=lower_bound(ans.begin(),ans.end(),y[i])-ans.begin()+1;
            join(t1,t2);
        }
        int sum=0;
        for(int i=1;i<=cnt;i++)
        {
            if(fa[i]==i)
            {
                if(tag[i])sum+=sz[i];
                else sum+=sz[i]-1;
            }
        }
        printf("Case #%d: %d\n",++cas,sum);
    }
    return 0;
}
/*
100
3
100 99
99 100
98 98
*/