starusc @ 2017-10-02 08:59:50

#include<iostream>
using namespace std;
int a[1510][1510]={0},b[1510]={0};
int n,e,f,g=1000,h=0,k=0;
void dfs(int x){
    cout<<x<<endl;
    for(int i=g;i<=h;i++){
        if(a[x][i]>0){
            a[x][i]--;
            a[i][x]--;
            dfs(i);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>e>>f;
        if(e<g)g=e;
        if(f>h)h=f;
        b[e]++;
        b[f]++;
        a[e][f]++;
        a[f][e]++;
    }
    for(int i=g;i<=h;i++)
        if(b[i]%2==1){
            k=i;
            break;
        }
    if(k!=0)dfs(k);
    else dfs(g);
    return 0;
}

by interestingLSY @ 2017-10-04 21:24:21

这样改就对了

欧拉回路需要在回溯时记录顶点，并倒序输出

#include<iostream>
using namespace std;
int a[1510][1510]={0},b[1510]={0};
int n,e,f,g=1000,h=0,k=0;
int top = 0;
int ans[1510];
void dfs(int x){
    for(int i=g;i<=h;i++){
        if(a[x][i]>0){
            a[x][i]--;
            a[i][x]--;
            dfs(i);
        }
    }
    ans[++top] = x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>e>>f;
        if(e<g)g=e;
        if(f>h)h=f;
        b[e]++;
        b[f]++;
        a[e][f]++;
        a[f][e]++;
    }
    for(int i=g;i<=h;i++)
        if(b[i]%2==1){
            k=i;
            break;
        }
    if(k!=0)dfs(k);
    else dfs(g);
    for( int i = top ; i >= 1 ; i-- )  cout << ans[i] << endl;
    return 0;
}

by 那便一去不回 @ 2021-01-25 16:17:12

@interestingLSY 大神能帮我解释一下为什么直接输出不行吗?