题意

Link
给定一个 $ n $ 个点, $ m $ 条边的无向连通图,可以加入新的边,要求给每条边定向,使得每个点的出度与入度均为偶数,在此前提下要求加入的边最少. $ n \leq 10^5,m \leq 2 \times 10^6$

分析

由于出度入度都为偶数, 所以在定向前的无向图中所有点的度均为偶数, 并且总边数为偶数. 由于无向图所有点的度为偶数, 所以初始无向图中度为奇数的点有偶数个, 每次任取两个点连边即可. 又总边数为偶数, 因此若此时总边数为奇数, 加一条边 $ \left ( u, u \right ) $即可, $ u $的度数仍为偶数.

此时将所有边任意定向然后再调整每条边的方向以满足题意.

由于总边数为偶数, 因此所有点入度和为偶数, 因此入度出度为奇数的点有偶数个, 考虑每次任取其中两个点 $ u,v $ 使其符合题意. 由于将 $ u \leftarrow v $ 上的所有边反向不影响路径上其他点的入度和出度, $ u,v $ 的出度和入度的奇偶性均发生了变化, 则 $ u,v $ 符合题意

由于初始为连通无向图, 因此可以取原图任意生成树 $ T $ , 反向路径时将 $ u,v $ 之间的树上路径反向即可. 这可以用树剖维护, 时间复杂度 $ \mathcal{O} \left ( nlog_2^2n \right ) $ , 这题有个欧拉回路的做法但是我不会

Code

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define rl register long long
#define N 200010
struct edge{ll u,v;}es[N<<1];
vector<ll> ns;
ll n,in[N],ot[N],hd[N],nxt[N<<1],t[N<<1],id[N<<1],cnt,fa[N],top[N],son[N],siz[N],dfn[N],up[N][20],dep[N],dfncnt,m;
inline ll ffa(rl a){return fa[a]==a?a:fa[a]=ffa(fa[a]);}
inline void add_edge(rl a,rl b,rl c){nxt[++cnt]=hd[a],t[cnt]=b,hd[a]=cnt,id[cnt]=c;}
struct ST{
    ll sum[N<<2],tg[N<<2];
    void pushdown(rl u,rl l,rl r){rl mid=(l+r)>>1;if(l!=r){sum[u<<1]+=tg[u]*(mid-l+1),sum[u<<1|1]+=tg[u]*(r-mid),tg[u<<1]+=tg[u],tg[u<<1|1]+=tg[u];}tg[u]=0;}
    void update(rl u,rl cl,rl cr,rl ql,rl qr,rl v){pushdown(u,cl,cr);if(cl>qr || cr<ql) return;if(cl>=ql && cr<=qr){sum[u]+=(cr-cl+1)*v,tg[u]+=v;return;}rl mid=(cl+cr)>>1;update(u<<1,cl,mid,ql,qr,v),update(u<<1|1,mid+1,cr,ql,qr,v),sum[u]=sum[u<<1]+sum[u<<1|1];}
    ll query(rl u,rl cl,rl cr,rl q){pushdown(u,cl,cr);rl mid=(cl+cr)>>1;if(cl==cr) return sum[u];return q<=mid?query(u<<1,cl,mid,q):query(u<<1|1,mid+1,cr,q);}
}T;
void dfs(rl u,rl fa){
    siz[u]=1,up[u][0]=fa,dep[u]=dep[fa]+1;
    for(rl i=1;i<20 && (1<<i)<dep[u];++i)
        up[u][i]=up[up[u][i-1]][i-1];
    for(rl p=hd[u],v;p;p=nxt[p]) if((v=t[p])!=fa)
        dfs(v,u),siz[u]+=siz[v],siz[v]>siz[son[u]]?son[u]=v:0LL;
}
void dfs2(rl u,rl fa,rl tp){
    top[u]=tp,dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],u,tp);
    for(rl p=hd[u],v;p;p=nxt[p]) if((v=t[p])!=fa && v!=son[u])
        dfs2(v,u,v);
}
inline ll lca(rl a,rl b){
    if(dep[a]<dep[b]) swap(a,b);
    rl mn=dep[a]-dep[b];
    for(rl i=19;i>=0;--i) if((1<<i)&mn)
        a=up[a][i];
    if(a==b) return a;
    for(rl i=19;i>=0;--i) if(up[a][i]!=up[b][i])
        a=up[a][i],b=up[b][i];
    return up[a][0];
}
void update(rl a,rl b){
    if(dep[a]<dep[b]) swap(a,b);
    while(dep[a]>dep[b]){
        if(dep[top[a]]<=dep[b]) T.update(1,1,n,dfn[b]+1,dfn[a],1);
        else T.update(1,1,n,dfn[top[a]],dfn[a],1);
        a=up[top[a]][0];
    }
}
void dfs3(rl u,rl fa){
    for(rl p=hd[u],v;p;p=nxt[p]) if((v=t[p])!=fa){
        if(T.query(1,1,n,dfn[v])%2) swap(es[id[p]].u,es[id[p]].v);
        dfs3(v,u);
    }
}
int main(){
    scanf("%lld %lld",&n,&m);
    for(rl i=1;i<=n;++i)
        fa[i]=i;
    for(rl i=0;i<m;++i)
        scanf("%lld %lld",&es[i].u,&es[i].v),++ot[es[i].u],++in[es[i].v];
    for(rl i=1;i<=n;++i) if((in[i]+ot[i])%2)
        ns.push_back(i);
    for(rl i=0;i<ns.size()/2;++i)
        es[m++]=(edge){ns[i<<1],ns[i<<1|1]},++in[ns[i<<1|1]],++ot[ns[i<<1]];
    for(rl i=0;i<m;++i) if(ffa(es[i].u)!=ffa(es[i].v))
        add_edge(es[i].u,es[i].v,i),add_edge(es[i].v,es[i].u,i),fa[ffa(es[i].u)]=ffa(es[i].v);
    if(m&1){
        es[m++]=(edge){1LL,1LL};
        ++in[1],++ot[1];
    }
    dfs(1,0),dfs2(1,0,1);
    ns.clear();
    for(rl i=1;i<=n;++i) if(in[i]%2)
        ns.push_back(i);
    for(rl i=0,u,v,j;i<ns.size()/2;++i){
        u=ns[i<<1],v=ns[i<<1|1];
        j=lca(u,v);
        update(u,j),update(v,j);
    }
    dfs3(1,0);
    printf("%lld\n", m);
    for(rl i=0;i<m;++i)
        printf("%lld %lld\n", es[i].u,es[i].v);
    return 0;
}
文章目录