初始超时做法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N=100010,M=400010;
int h[N],e[M],ne[M],idx;
int din[N],dout[N];
int n,m,type;
bool used[N];
int ans[M],cnt;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    for(int i=h[u];~i;i=ne[i]){
        if(used[i])continue;
        used[i]=true;
        if(type==1)used[i^1]=true;
        dfs(e[i]);

        if(type==1){
            int t=i/2+1;
            if(i&1)t=-t;
            ans[++cnt]=t;
        }
        else ans[++cnt]=i+1;
    }    
}

int main()
{
    scanf("%d%d%d",&type,&n,&m);
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(type==1)add(b,a);
        din[b]++,dout[a]++;
    }

    if(type==1){
        for(int i=1;i<=n;i++){
            if(din[i]+dout[i]&1){
                puts("NO");
                return 0;
            }
        }
    }
    else {
        for(int i=1;i<=n;i++){
            if(din[i]!=dout[i]){
                puts("NO");
                return 0;
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(h[i]!=-1){
            dfs(i);
            break;
        }
    }

    if(cnt<m){
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i=cnt;i;i--)printf("%d ",ans[i]);
    puts("");
    return 0;
}

优化做法

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=100010,M=400010;
int h[N],e[M],ne[M],idx;
bool used[M];
int n,m;
int type;
int din[N],dout[N];
int ans[M],cnt;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    for(int& i=h[u];~i;){
        if(used[i]){
            i=ne[i];
            continue;
        }

        used[i]=true;
        if(type==1)used[i^1]=true;

        int t;
        if(type==1){
            t=i/2+1;
            if(i&1)t=-t;
        }
        else t=i+1;

        int j=e[i];
        i=ne[i];

        dfs(j);

        ans[++cnt]=t;
    }    
}

int main()
{
    scanf("%d%d%d",&type,&n,&m);
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(type==1)add(b,a);
        din[b]++,dout[a]++;
    }

    if(type==1){
        for(int i=1;i<=n;i++){
            if(din[i]+dout[i]&1){
                puts("NO");
                return 0;
            }
        }   
    }
    else {
        for(int i=1;i<=n;i++){
            if(din[i]!=dout[i]){
                puts("NO");
                return 0;
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(h[i]!=-1){
            dfs(i);
            break;
        }
    }
    if(cnt<m){
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i=cnt;i;i--)cout<<ans[i]<<" ";
    puts("");
    return 0;
}