【Gym 100812C】Story of Princess (走完图所有边)

#include <cstdio>
#define N 100005
#define M 400005
using namespace std;

int n,m;
struct edge{
    int to,next;
    bool vis;
}e[M];
int head[N],cnt=2;

int du[N];//点的度数
int idx[N];//点在s中的序号
int ans,sub;//sub是可以减去的步数
int s[M];//存储答案链表
int nxt[M];//nxt[i]代表s[i]在链表中的下一个

void add(int u,int v){
    ++du[u];
    e[cnt]=(edge){v,head[u]};
    head[u]=cnt++;
}

void dfs(int x){
    nxt[ans]=ans+1;
    s[++ans]=x;
    idx[x]=ans;
    for(int &i=head[x];i;i=e[i].next){
        if(e[i].vis)continue;
        e[i].vis=e[i^1].vis=true;
        --du[x],--du[e[i].to];
        dfs(e[i].to);
        break;//每次只找出一条连续的链
    }
}

//找出欧拉回路
void dfs2(int x){
    for(int &i=head[x];i;i=e[i].next){
        if(e[i].vis)continue;
        e[i].vis=e[i^1].vis=true;
        --du[x],--du[e[i].to];
        dfs2(e[i].to);
    }
    nxt[ans]=ans+1;
    s[++ans]=x;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;++i){
        scanf("%d%d",&u,&v);
    add(u,v);add(v,u);
    }
    for(int i=1;i<=n;++i)
        if(du[i]&1)dfs(i);//走完所有的链

#ifdef _LOCAL
    for(int i=1;i<=ans;++i)printf("%d ",s[i]);
    puts("");
#endif

    for(int i=1;i<=n;++i)
    if(idx[i]&&du[i]){//把链上连着的环走完
        int t=ans;
        dfs2(i);
        nxt[idx[i]]=t+2;
        nxt[ans]=idx[i]+1;
        nxt[t]=0;
        ++sub;
    }

    for(int i=1;i<=n;++i)
        if(du[i])dfs2(i);//走完剩下的环

    printf("%d\n",ans-sub);
    if(ans-sub)for(int p=1;p;p=nxt[p])printf("%d ",s[p]);
    return 0;
}