2020牛客暑期多校训练营（第八场）I题 Interesting Computer Game（离散化+图论dfs）

Interesting Computer Game

题目大意：给出n对 a[i] , b[i] ，每次可以选择一个之前没有选择过的数，问最多能选几个。

解题思路：

因为每次只能从a[i] b[i]中选一个，可以把a[i]和b[i]用一条线连接起来，只能选择该线左端点或者右端点，然后把n对a[i] b[i]都链接起来，这样就形成了多个联通块。
对于每个联通块进行单独判断，可以把它当成成类似树的数据结构，有n个节点，大于等于n-1条边，如果是n-1条边的话，显然只能选择n-1个点，如果大于n-1条边的话，
那么这n个节点就都可以选中啦(可以画个图模拟一下)，要注意这个是在单个联通块中进行的 。

最后要注意一下数据范围很大，要进行一下离散化。

    //离散化模板，敲起来挺顺手的
    int getid(int x){
        return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1; //下标从1开始
    }

    ve.push_back(x[i]);
    sort(ve.begin(),ve.end());
    ve.erase(unique(ve.begin(),ve.end()),ve.end());
    x[i]=getid(x[i]);

Code:

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 9654234
#define ll long long
using namespace std;
const int maxn=500007;
vector<int> ve,ed[maxn];
int x[maxn],y[maxn],vis[maxn];
int ans,bian,dian;

int getid(int x){
    return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
}

void dfs(int x){
    bian+=ed[x].size();
    dian++;
    for(auto it:ed[x]){
        if(!vis[it]){
            vis[it]=1;
            dfs(it);
        }
    }
}

void solve(int i){
    bian=0;
    dian=0;
    vis[i]=1;
    dfs(i);
    if(bian/2>=dian) ans+=dian; //边记录了两次，要/2
    else ans+=dian-1;
}

int main ()
{
    int t,n,k;
    cin>>t;
    for(int k=1;k<=t;k++)
    {
        ans=0;
        ve.clear();
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>x[i]>>y[i];
            ve.push_back(x[i]);
            ve.push_back(y[i]);
        }
        sort(ve.begin(),ve.end());
        ve.erase(unique(ve.begin(),ve.end()),ve.end());
        int sz=ve.size();
        for(int i=0;i<=sz;i++) ed[i].clear(),vis[i]=0;
        for(int i=1;i<=n;i++){
            x[i]=getid(x[i]);
            y[i]=getid(y[i]);
//            cout<<x[i]<<" "<<y[i]<<endl;
            ed[x[i]].push_back(y[i]);
            ed[y[i]].push_back(x[i]);
        }

        for(int i=1;i<=sz;i++){
            if(!vis[i]) solve(i);
        }

        cout<<"Case #"<<k<<": "<<ans<<endl;        
    }
}