CF527E Data Center Drama 题解

· · 题解

Solution

感觉联想到欧拉回路有点过于强大了。。。

给出一个不需要欧拉回路的算法。

问题转化为：保证所有点的入度和无向图上的度数都是偶数。

先去掉所有自环，默认把入度增加 1。并且将原无向图上度数是奇数的点两两配对并连边。这时候已经满足无向图上的度数都是偶数。而注意到

m = \sum_{u \in V} \mathrm{degin}_u

（这里的 m 是增加配对边之后的边数，包括之前删掉的自环）

因此如果 2 \nmid m，还需要增加一条边，方便起见就增加自环，然后再把它去掉。

容易发现，我们新增的边都是必要的。下面构造地证明解一定存在。

随便求出原图的一棵 DFS 树。

将非树边的指向随便定。

自底向上确定每条树边的方向。具体的，如果儿子的入度为奇数，树边就指向儿子，否则指向父亲。

而根节点的入度等于 m 减去其他所有点的入度，必定为偶数。

因此我们找到了一个合法的方案。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,m,deg[MAXN],dout[MAXN],vis[MAXN],dep[MAXN];
vector<int> G[MAXN],T[MAXN];
vector<pair<int,int>> ans;
void dfs(int u,int f) {
    dep[u]=dep[f]+1,vis[u]=1;   
    int cnt=0;
    for(auto v:G[u]) {
        if(v==f) if(!cnt) {cnt=1;continue;}
        if(vis[v]&&dep[v]<dep[u]) ans.push_back({u,v}),dout[u]++;   
        if(vis[v]) continue ;
        T[u].push_back(v),dfs(v,u);
    }
    return ;
}
void solve(int u,int f) {
    for(auto v:T[u]) {
        solve(v,u);
        if(dout[v]&1) ans.push_back({v,u});
        else ans.push_back({u,v}),dout[u]++;
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,m) {
        int u,v;
        cin>>u>>v;
        if(u==v) {
            ans.push_back({u,v}),dout[u]++;
            continue ;  
        }
        G[u].push_back(v),G[v].push_back(u),deg[u]++,deg[v]++;
    }
    vector<int> vc;
    ffor(i,1,n) if(deg[i]&1) vc.push_back(i);
    ffor(i,1,vc.size()/2) {
        int u=vc[2*i-2],v=vc[2*i-1];
        G[u].push_back(v),G[v].push_back(u);    
        m++;
    }
    if(m&1) m++,ans.push_back({1,1}),dout[1]++;
    dfs(1,0);
    solve(1,0);
    cout<<m<<'\n';
    for(auto pr:ans) cout<<pr.first<<' '<<pr.second<<'\n';
    return 0;
}