51nod1967 路径定向 Fleury

题目传送门

题解

几乎是Fleury模板题。

一开始我们把图看作无向图，然后对于度为奇数的点增边，使得整个图的所有点都是偶数的。

然后跑一遍欧拉回路 Fleury ，所有的边就定向好了~

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=1e5+,M=3e5*+;

int fst[N],n,m,cnt=,die[M],ans[M],totdo;

struct Edge{

    int x,y,nxt,f,bh;

    void set(int a,int b,int BH,int F){

        x=a,y=b,bh=BH,f=F;

    }

}e[M];

void read(int &x){

    char ch=getchar();

    x=;

    while (!(''<=ch&&ch<=''))

        ch=getchar();

    while (''<=ch&&ch<=''){

        x=x*+ch-;

        ch=getchar();

    }

}

void Make_Disedge(){

    totdo=;

    int prev=,in[N],m_=m;

    memset(in,,sizeof in);

    for (int i=;i<=cnt;i++)

        in[e[i].y]++;

    for (int i=;i<=n;i++){

        if (in[i]%==){

            totdo++;

            continue;

        }

        if (prev==)

            prev=i;

        else {

            e[++cnt].set(prev,i,++m_,);

            e[cnt].nxt=fst[prev],fst[prev]=cnt;

            e[++cnt].set(i,prev,m_,);

            e[cnt].nxt=fst[i],fst[i]=cnt;

            prev=;

        }

    }

}

void Flenry(int rt){

    for (int i=fst[rt];i;i=e[i].nxt){

        if (die[e[i].bh]){

            fst[rt]=e[i].nxt;

            continue;

        }

        die[e[i].bh]=;

        ans[e[i].bh]=e[i].f;

        fst[rt]=e[i].nxt;

        Flenry(e[i].y);

        break;

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for (int i=;i<=m;i++){

        int a,b;

        read(a),read(b);

        e[++cnt].set(a,b,i,);

        e[cnt].nxt=fst[a],fst[a]=cnt;

        e[++cnt].set(b,a,i,);

        e[cnt].nxt=fst[b],fst[b]=cnt;

    }

    Make_Disedge();

    for (int i=;i<=n;i++)    Flenry(i);

    printf("%d\n",totdo);

    for (int i=;i<=m;i++)

        putchar(ans[i]+'');

    return ;

}