2020牛客多校第八场 I-Interesting Computer Game

题意： 给定 $n$ 组数，每组两个数， $a_i$ 和 $b_i$ 。在第 $i$ 组数时，有三种操作：可以不选，如果 $a_i$ 未被选过，可以选择 $a_i$ ，或者 $b_i$ 没被选过，可以选择 $b_i$ ，但是一次最多选一个数。现在问 $n$ 组数最多可以选择多少个。

题解： 考虑将 $a_i$ 和 $b_i$ 连条边。假设最后有 $k$ 个连通分量，考虑第 $j$ 个连通分量，如果该连通分量的边数不小于点数，则加上点数，否则加上点数减 $1$ 。
可以这么理解：考虑一个连通分量：

$1\ 2$
$2 \ 3$
$3 \ 4$
$4\ 4$
在这里插入图片描述
图中每选取一个点，就要切割点这个点的一条边。因此当这个图中有 $x$ 点， $x-1$ 边时，只能选 $x-1$ 个点，而当边数大于等于点数时，优先选择边数等于 $1$ 的点，最后会剩下的点边数多于 $1$ 的点再被选择。所以无论如何所有点都会被选择。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
template<typename T>
inline T Read() {
    T x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();} 
    return x * f;
}

#define read() Read<int>()
#define readl() Read<long long>()

const int N = 2e5 + 10;
vector<int> g[N];
int q[N], x[N], y[N];
int gp, res;
int b_s(int x) {
    int l = 1, r = gp;
    while(l < r) {
        int mid = l + r >> 1;
        if(q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int vis[N], edge, point;
void dfs(int u) {
    vis[u] = 1;
    edge += g[u].size();
    ++point;
    for(auto it : g[u]) {
        if(vis[it]) continue;
        dfs(it);
    }
}

void solve(int num) {
    int n = read(), last = n * 2;
    for(int i = 1; i <= n; i++) x[i] = read(), y[i] = read();
    for(int i = 1; i <= n; i++) q[i * 2 - 1] = x[i], q[i * 2] = y[i];
    sort(q + 1, q + 1 + last);

    gp = 0;
    for(int i = 1; i <= last; ) {
        q[++gp] = q[i];
        int j = i + 1;
        while(j <= last && q[i] == q[j]) ++j;
        i = j; 
    }
    last = gp;

    for(int i = 1; i <= last; i++) g[i].clear(), vis[i] = 0;
    for(int i = 1; i <= n; i++) {
        x[i] = b_s(x[i]);
        y[i] = b_s(y[i]);
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }

    res = 0;
    for(int i = 1; i <= last; i++) 
        if(!vis[i]) {
            edge = 0;
            point = 0;

            dfs(i);

            edge /= 2;
            res += point - 1;
            if(edge >= point) ++res;
        }

    printf("Case #%d: %d\n", num, res);
}

int main()
{
    int T = read();
    for(int i = 1; i <= T; ++i) {
        solve(i);
    }
}