题目链接：Codeforces 1186F

Vus 有一张包含 $n$ 个点和 $m$ 条边的图。设 $d_i$ 表示第 $i$ 个点的度数。他需要保留 $\left\lceil\frac{n + m}{2}\right\rceil$ 条边，设 $f_i$ 表示新图中第 $i$ 个点的度数。他需要对于所有的 $i$ 保证 $\left\lceil\frac{d_i}{2}\right\rceil \le f_i$。

请你帮 Vus 保留一些边使这张图满足条件。

数据范围：$1 \le n \le 10 ^ 6$，$0 \le m \le 10 ^ 6$。

Solution

解法 1

考虑随机吊打标算！

我们对边进行随机打乱，然后从前往后扫一遍，只要能删除当前边就直接删除。如果最后剩余的边数满足条件则直接输出；否则重新打乱……

事实上出题人是拿脚造的数据，随机不但能通过本题，而且只需要 $500\ \text{ms}$！

解法 2

考虑标算。

我们新建一个虚点 $0$，对于所有度数为奇数的点和 $0$ 点连一条边，设新图中边的数量为 $k$ 则一定有 $k \le n + m$。发现新图中每个点的度数都是偶数，则一定可以找到一条欧拉回路。考虑一种删边方式：将欧拉回路中偶数位置的边删除，这样剩余边数为 $\left\lceil\frac{k}{2}\right\rceil = \left\lceil\frac{n + m}{2}\right\rceil$ 满足条件。

接下来证明每个点的度数「相对新图」是满足条件的。对于欧拉回路 $e_1, e_2, \dots, e_k$ 中任意相邻的两条边 $e_i, e_{i + 1}$，假设 $e_i = (u, v), e_{i + 1} = (v, w)$，这两条边中会且仅会删除其中一条边。那么 $v$ 的度数只会减少 $1$，正确性得证（对于第 $1, n$ 条边，我们考虑 $(e_n, e_1)$ 和 $(e_n, e_1)$ 这两组边）。

上文特别强调了「相对新图」，由于新图中存在虚边，这些边对于度数会有影响。于是在删去虚边后有可能不满足条件（反例比比皆是），我们在原方法上贪心删边：

• 如果第 $i$ 条边为虚边，那么不进行任何修改。
• 如果第 $i$ 条边为实边，且在原方案中需要删除。那么贪心地考虑第 $i - 1, i + 1$ 条边。如果任意一条为虚边则贪心删除虚边，而不删除实边；否则删除实边。

最后还有一个问题：一条虚边为什么不会被删除多次？读者自证不难。显然一旦出现虚边则一定连续出现两次。

对于原图不一定连通，所以要对每个连通块分别计算。

时间复杂度：$O(n + m)$。

Code

解法 1

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

const int N = 1e6 + 5;

int n, m, d[N], D[N], f[N];
bool del[N];

struct Edge {
    int u, v;
} e[N];

int main() {
    srand(time(0) + ('Q' + 'Y' + 'A' + 'K' + 'I' + 'O' + 'I'));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &e[i].u, &e[i].v);
        d[e[i].u]++, d[e[i].v]++;
    }
    for (int i = 1; i <= n; i++) {
        D[i] = d[i] / 2 + (d[i] & 1);
    }
    int tar = (n + m) / 2 + ((n + m) & 1);
    while (true) {
        std::random_shuffle(e + 1, e + m + 1);
        std::copy(d + 1, d + n + 1, f + 1);
        std::fill(del + 1, del + m + 1, false);
        int tot = 0;
        for (int i = 1; i <= m; i++) {
            int u = e[i].u, v = e[i].v;
            if (f[u] > D[u] && f[v] > D[v]) {
                del[i] = true;
                f[u]--, f[v]--;
            } else {
                tot++;
            }
        }
        if (tot <= tar) {
            printf("%d\n", tot);
            for (int i = 1; i <= m; i++) {
                if (!del[i]) {
                    printf("%d %d\n", e[i].u, e[i].v);
                }
            }
            return 0;
        }
    }
    return 0;
}

解法 2

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 1e6 + 5, M = 4e6 + 5;

int n, m, tot = 1, cnt, deg[N], lnk[N], ter[M], nxt[M], idx[M];
bool visNode[N], visEdge[M], del[M];
std::vector<int> p;

void addEdge(int u, int v, int x) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, idx[tot] = x;
}
bool isReal(int x) {
    return x <= m;
}
void dfs1(int u) {
    visNode[u] = true;
    if (deg[u] & 1) {
        cnt++;
        addEdge(u, n + 1, m + cnt);
        addEdge(n + 1, u, m + cnt);
    }
    for (int i = lnk[u]; i; i = nxt[i]) {
        if (!visNode[ter[i]]) dfs1(ter[i]);
    }
}
void dfs2(int u) {
    for (int &i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i], x = idx[i];
        if (visEdge[x]) continue;
        visEdge[x] = true;
        dfs2(v);
        p.emplace_back(x);
    }
}
void solve(int x) {
    dfs1(x);
    dfs2(x);
    int len = p.size();
    if (len == 0) return;
    std::reverse(p.begin(), p.end());
    p.push_back(p.front());
    for (int i = 1; i < len; i += 2) {
        if (p[i] <= m) {
            if (p[i - 1] > m && !del[p[i - 1]]) {
                del[p[i - 1]] = true;
                del[p[i]] = false;
            } else if (p[i + 1] > m && !del[p[i + 1]]) {
                del[p[i + 1]] = true;
                del[p[i]] = false;
            } else {
                del[p[i]] = true;
            }
        } else {
            del[p[i]] = true;
        }
    }
    lnk[n + 1] = 0, tot = m + m + 1, p.clear();
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v, i);
        addEdge(v, u, i);
        deg[u]++, deg[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!visNode[i]) solve(i);
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans += (!del[i]);
    printf("%d\n", ans);
    for (int i = 2; i <= tot; i += 2) {
        if (!del[idx[i]]) {
            printf("%d %d\n", ter[i + 1], ter[i]);
        }
    }
    return 0;
}