CF527E Data Center Drama

链接CF527E Data Center Drama

题目大意：给你一个无向图，要求加最少的边，然后给这些无向图的边定向,使得每一个点的出入度都是偶数。
\(n<=10^5,n\leq 2*10^5\)
考虑欧拉回路，欧拉回路出度等于入度，如果把某一个反向，出入度都是偶数。
所以对两个奇数点加边，如果最后\(m\)是奇数就再加一个自环，最后做\(Dfs\)欧拉回路即可。
这里学到了一个姿势：

void Dfs(R i){

    for(R &k=hd[i];k;k=nt[k])

        if(!vis[k]){

            vis[k]=vis[k^1]=1;

            int p=k;Dfs(to[p]);

            if((++num)&1)printf("%d %d\n",i,to[p]);

            else printf("%d %d\n",to[p],i);

        }

}

这里的欧拉回路是一个压栈的过程，如果不\(Dfs\)之后再输出的化，就会错，只有把整个欧拉回路扣出来之后才能确定奇偶性质。
取地址是当前弧优化，因为前面的链条已经被遍历过了，如果再经过这个点就没有必要再经过了。
代码：

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=500001;

int n,m,ans,cnt,las,u,v,num;

int du[N],hd[N],vis[N],to[N],nt[N];

void link(R f,R t){nt[++cnt]=hd[f],to[cnt]=t,hd[f]=cnt;}

int gi(){

    R x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

void Dfs(R i){

    for(R &k=hd[i];k;k=nt[k]){

        if(!vis[k]){

            vis[k]=vis[k^1]=1;

            int p=k;Dfs(to[p]);

            if((++num)&1)printf("%d %d\n",i,to[p]);

            else printf("%d %d\n",to[p],i);

        }

    }

}

int main(){

    n=gi(),ans=m=gi(),cnt=1;

    for(R i=1;i<=m;++i){

        u=gi(),v=gi(),du[u]++,du[v]++;

        link(u,v),link(v,u);

    }

    for(R i=1;i<=n;++i)

        if(du[i]&1){

            if(las)link(i,las),link(las,i),las=0,ans++;

            else las=i;

        }

    if(ans&1)link(1,1),link(1,1),ans++;

    printf("%d\n",ans),Dfs(1);

    return 0;

}

巴特西

CF527E Data Center Drama

链接CF527E Data Center Drama

最新文章

热门文章